Recursion. I don't understand proof.

Question

Theorem

Let $a_0$ and $a_1$ be given and let $a_2,a_3,...$ be defined by the recurrence relation $a_n=Aa_{n-1} + Ba_{n-2} (n>1)$ where $A$ and $B$ are constants. Then let $\alpha, \beta$ be the roots of the quadratic equation $x^2 = Ax + B$

It then

if $\alpha \neq \beta $ there exist constants $c, d$ with $a_n = c\alpha^n + d\beta^n$ for each $ n \ge 0 $

Proof:

It is easy to check that, whatever the value of the constants $c$ and $d$, the given formula satisfies $a_n = Aa_{n-1} + Ba_{n-2} = A(c\alpha^{n-1} + d\beta^{n-1} ) + B(c\alpha^{n-2} + d\beta^{n-2}) $

I can't understand why the above is true for any $c,d$

Answer 1

From $\alpha^2=A\alpha+B$, we immediately get that $\alpha^n=A\alpha^{n-1}+B\alpha^{n-2}$ for all $n\ge 2$. Likewise, $\beta^n=A\beta^{n-1}+B\beta^{n-2}$. Since both equations are linear, it does not hurt if we multiply them by constant factors $c,d$ and then add, i.e., we have $$(c\alpha^n+d\beta^n)=A( c\alpha^{n-1}+d\beta^{n-1})+B( c\alpha^{n-2}+d\beta^{n-2})$$ for all $n\ge 2$. While this holds for an arbitrary choice of $c,d$, we do need special values of $c,d$ to adjust to the initial conditions: $$a_0=c\alpha^0+d\beta^0=c+d,\qquad a_1=c\alpha^1+d\beta^1=c\alpha+d\beta.$$ These are two equalities in two unknowns, and by the very fact that $\alpha\ne \beta$, this system has a unique solution. So with this particular choice of $c,d$, if we let $b_n=c\alpha^n+d\beta^n$, then we have $b_0=a_0$, $b_a=a_1$, and by the recursion equatlities $b_n=cb_{n-1}+db_{n-2}=ca_{n-1}+da_{n-2}=a_n$ follows by induction also for $n\ge 2$.