0

Suppose that $f(x) = x^2 - ax - b$ is the characteristic polynomial of a recurrence equation: $$ u(n) = au(n-1) + bu(n-2) \quad (n \geq n_0 + 2). $$

a) Prove that if $f(x)$ has distinct non-zero roots $\alpha_1$ and $\alpha_2$ then any solution of the equation has the form $u(n) = C_1 \alpha_1^n + C_2 \alpha_2^n$ and constants $C_1$ and $C_2$ are determined uniquely.

b) Prove that if $f(x)$ has double root $\alpha$ then any solution of the equation has the form $u(n) = C_1 \alpha^n + C_2n \alpha^n$ and constants $C_1$ and $C_2$ are determined uniquely, if $\alpha \neq 0$

I tried to solve that problem using mathematical induction, the main difficulty for me is that I can't prove the basis of induction.

Sammy Black
  • 25,273
Arthur_Kitsuragi
  • 137

1 Answers1

1

This is tricky because you can't prove by induction that "$\exists C_1,C_2,u(n)=C_1\alpha_1^n+C_2\beta_2^n$" for all $n$ because you allow $C_1$ and $C_2$ to depend on $n$. You must first find $C_1$ and $C_2$ and then show by induction that $u(n)=C_1\alpha_1^n+C_2\beta_2^n$ for all $n$. You have two constants so you need two equations to define these, namely the base case : such constants should satisfy $$ \left\{\begin{aligned}&C_1+C_2=u(0) \\ &C_1\alpha_1+C_2\alpha_2 =u(1)\end{aligned}\right. $$ The discriminant of this system is $\alpha_2-\alpha_1\neq 0$ so there is a unique solution. Now the base case of the induction is trivial because of the choice of $C_1$ and $C_2$ and the induction follows from the fact that $f(\alpha_1)=f(\alpha_2)=0$ (I'll leave the details for you). If now $\alpha_1=\alpha_2$ you do the same but with the given form, the system you aim to solve is now $$ \left\{\begin{aligned}&C_1=u(0) \\ &C_1\alpha_1+C_2\alpha_2 =u(1)\end{aligned}\right. $$ and you can conclude in the same fashion.

Tuvasbien
  • 8,907