0

Prove by induction that the only solutions to $au_{n+2}+bu_{n+1}+cu_n=0, n\geq0$ are $u_n=A\alpha ^n+ B\beta ^n$ where $\alpha$ and $\beta$ are solutions to $ax^2+bx+c=0$ and $b^2\neq 4ac$ and $A=\frac{u_1 - \beta u_0}{\alpha-\beta}, B=\frac{u_1-\alpha u_0}{\beta-\alpha}$

It can easily be shown that the above is a solution, but I am having a hard time showing it is the only solution(using induction).

Suppose $f_n$ is a solution, then $g_n=u_n+f_n$ is a solution and we RTP $f_n=0$. Assume true for $n=k,k+1$

$af_{n+2}+bf_{n+1}+cf_n=0$

$\iff cf_n=0$

$\iff f_n=0$

$P(k)$ and $ P(k+1) \implies P(k+2)$

However, now I don't really have any options for the base case since I don't know anything about $g_n$

witten_s
  • 54
  • Try and use the second principle of mathematical induction. – Daniel Akech Thiong Dec 18 '20 at 11:40
  • @akech But I still need a base case? – witten_s Dec 18 '20 at 12:20
  • (1) what does "RTP" mean? (2) They mean the only solution given the starting values of $u_0$ and $u_1$ (note that $A$ and $B$ depend on these two values). So you already know that $f_0 = f_1 = 0$ in your proof. – Paul Sinclair Dec 18 '20 at 19:06
  • @PaulSinclair (1) Required to prove (2) I'm not sure if I follow. We know $g_0=u_0+f_0$ and $g_1=u_1+f_1$ but since we don't know anything about $g_0$ and $g_1$, I'm not sure how we continue. – witten_s Dec 18 '20 at 19:50
  • I think I see the point of confusion. $g$ is assumed to be a solution to the recurrence relation, but I did not assume(or consider) it had the same starting values, that would be $g_0=u_0$ $g_1=u_1$. But it makes sense they must agree on all values to be the same sequence, thanks. – witten_s Dec 18 '20 at 19:53

0 Answers0