The roots of a second order recurrence relation $a_n = A a_{n-1} + B a_{n-2}$

Question

Suppose you have a second order recurrence relation with constant coefficients defined as follows: \begin{cases} a_n = A a_{n-1} + B a_{n-2}, n = 2, 3, ...\\ a_0, a_1 \text{ are given initial conditions} \end{cases} Then $\alpha, \beta$, $\alpha \neq \beta$, are the roots of equation $x^2 = Ax + B$, and

$a_n = K_1 \alpha^n + K_2 \beta^n, n \geq 0$,

for constants $K_1, K_2$ that are uniquely determined by the initial values.

Now my question, how do I show that $\alpha \beta = -B$ and $\alpha + \beta = A$?

I tried writing using the above definition by writing some things out, but it did not get me far. So I am not sure how else to approach it.

I also tried using the generating function: $f(x) = \cfrac{(a_1 -A a_o)x + a_o}{1 - Ax - Bx^2}$, unfortunately that also did not get me far.

Answer 1

This result is most easily gotten by factoring your polynomial into linear terms, then recombining them. In general, these are known as Vieta's formulas.

The proof is fairly easy: let $\alpha,\beta$ be the roots of $x^2+bx+c$. First, as a common result, we have $$(x-\alpha)(x-\beta)=x^2+bx+c.$$ This is the most difficult part of the theorem to prove, though it's fairly intuitive; you can establish this just by noting that if $P(x)$ is a polynomial and $a$ is a root, then $(x-a)$ divides $P(x)$, and this follows most directly by using synthetic division and most easily by using a change of variables. In any case, applying this fact twice and noting that the coefficient of $x^2$ is $1$ on both sides gives the desired equality.

Now, you just expand the left hand side: $$x^2-(\alpha+\beta)x+\alpha\beta = x^2+bx+c$$ This holds for every $x$. One can prove - for instance, by evaluating this equation at $x=0,1,2$ and reducing the three resulting equations or by differentiating - that this implies that all the coefficients on one side are equal to the corresponding ones on the other side. Thus $$1=1$$ $$-(\alpha+\beta)=b$$ $$\alpha\beta = c.$$ Which are the formulas you are looking for. This extends for polynomials with any number of variables. To get the specific form you are interested in, you just rearrange your polynomial to $x^2-Ax-B$.

Answer 2

Given that $\alpha$ and $\beta$ are roots of $x^2=Ax+B$,

we have $(x-\alpha)(x-\beta)=x^2-(\alpha+\beta)x+\alpha\beta=x^2-Ax-B$,

so it follows that $\alpha+\beta=A$ and $\alpha\beta=-B$.