0

For $p\in (0,1)$ and $q:=1-p$ find all the solutions $h=(h_i)_{i\in\mathbb{N}_0}$ of the recurrence relation $$ \begin{cases}h_0=1\\h_i=ph_{i+1}+qh_{i-1}, & \text{ for }i=1,2,...\end{cases} $$

First I assume that the solution is of the form $h_i=\lambda^i$. $$ -p\lambda^2+\lambda-q=0\Leftrightarrow\lambda^2-\frac{1}{p}\lambda+\frac{q}{p}=0 $$ This quadratic equation does have the two solutions $$ \alpha=\frac{1+\sqrt{1-4pq}}{2p},~~~\beta=\frac{1-\sqrt{1-4pq}}{2p}. $$

So $h_i=A\alpha^n+B\beta^n$ for constants $A,B$ is a solution.

By induction it can be shown that this is the general solution, right?

But my book says that for $p\neq q$ the general solution is $$ h_i=A+B\left(\frac{q}{p}\right)^i. $$ Do not see how getting this.

1 Answers1

1

If you use that $q=1-p$ you get that $\sqrt{1-4pq}=\sqrt{4p^2-4p+1}=\sqrt{(2p-1)^2}=2p-1$. Inserting this into your expressions for $\alpha$ and $\beta$ gives $\alpha = 1$ and $\beta = \frac{2-2p}{2p}=\frac{1-p}{p}=\frac{q}{p}$.

Sofia
  • 488
  • 2
  • 7
  • If $p<q$ then (because $0\leq h_i\leq 1 ~\forall i$) it has to be $B=0$ and because of the minimality of the solution it is $h_i=1$. But what is the case if $p>q$? My book says: Since $h_0=1$ we get $h_i=\left(\frac{q}{p}\right)^i+A\left(1-\left(\frac{q}{p}\right)^i\right)$. Can you explain me, why? –  Oct 25 '14 at 15:39
  • 1
    IF you set $i=0$ in the expression $h_i=A+B\left(\frac{q}{p}\right)^i$ you get $h_0 = A+B=1$, which gives $B=1-A$. Inserting this back into the expression for $h_i$ gives $h_i=A+(1-A)\left(\frac{q}{p}\right)^i$ and rearranging gives $h_i=\left(\frac{q}{p}\right)^i+A\left(1-\left(\frac{q}{p}\right)^i\right)$. – Sofia Oct 25 '14 at 15:45
  • Ah, great, so the minimal positive solution is $h_i=\left(\frac{q}{p}\right)^i$. What's if $p=q$? Why then general solution $h_i=A+Bi$? –  Oct 25 '14 at 15:54
  • If $p=q$ you get that $\alpha=\beta$, in which case the general solution is of the form $A\alpha^i+Bi\alpha^i$, and using $\alpha=1$ then gives $h_i = A+Bi$. – Sofia Oct 25 '14 at 15:56
  • Can you explain to me why the general solution is then of the form $A\alpha^i+Bi\alpha^i$? –  Oct 25 '14 at 16:09
  • The short explanation is that you need to find two linearly independent solutions. Usually $A\alpha^i$ and $B\beta^i$ are linearly independent, but if $\alpha=\beta$ they are not. You can then try to find a solution of the form $i\lambda^i$ the same way you tried to find a solution $\lambda^i$, which will give you two independent solutions. – Sofia Oct 25 '14 at 18:43
  • I tried to find a solution of the form $i\cdot\lambda^i$ and I got $\lambda_1=i\cdot \left(\frac{i+\sqrt{i^2-4p^2i^2+4p^2}}{2p(i+1)}\right)^i$ and $\lambda_2=i\cdot\left(\frac{i-\sqrt{i^2-4p^2i^2+4p^2}}{2p(i+1)}\right)^i$. But what do these two solutions have to do with the desired general solution $A+Bi$? –  Oct 29 '14 at 19:58
  • 1
    For a solution of the form $i\lambda^i$, $\lambda$ should not depend on $i$, so your expressions don't really make much sense. For a difference equation $Aa_{n+1}+Ba_n+Ca_{n-1}=0$, if $\lambda$ is a double root of the equation $A\lambda^2+B\lambda+C=0$ you may simply verify that $i\lambda^i$ in fact is a solution. – Sofia Oct 29 '14 at 22:46