# Proving Theorem regarding LHRCC (Linear Homogenous Recurrence Relations) with two distinct roots

RTP: Let $c_1$ and $c_2$ be real numbers. Suppose that $r^2 - rc_1 - c_2 = 0$ has two distinct roots $r_1$ and $r_2$. Then the sequence {$a_n$} is a solution of the recurrence relation $a_n = c_1a_{n-1} + c_2a_{n-2}$ if and only if $a_n = \alpha_1{r_1}^n + \alpha_2{r_2}^n$ for n = 0,1,2..., where $\alpha_1$ and $\alpha_2$ are constants.

I was given the clue this was a two part proof. Hopefully that helps!

• What have you tried? Do you have any thoughts about the problem? Is there some context that you think would help us? Commented Oct 16, 2017 at 15:53

Guide:

For backward direction:

If we already know that $a_n = \alpha_1r_1^n + \alpha_2r_2^n$ where $\alpha_1$ and $\alpha_2$ are constant,

$$c_1a_{n-1}+c_2a_{n-2}=c_1(\alpha_1r_1^{n-1}+\alpha_2r_2^{n-1})+c_2(\alpha_1r_1^{n-2}+\alpha_2r_2^{n-2})$$

Try to simplify this expression to $a_n$. You want to use the property that $r_1$ and $r_2$ are roots of a particular quadratic equation.

For forward direction:

If $a_n = c_1a_{n-1} + c_2a_{n-2}$,

we have $$\begin{bmatrix} a_{n-1} \\ a_n\end{bmatrix} = \begin{bmatrix} 0 & 1 \\ c_2 & c_1 \end{bmatrix}\begin{bmatrix} a_{n-2} \\ a_{n-1}\end{bmatrix}=\begin{bmatrix} 0 & 1 \\ c_2 & c_1 \end{bmatrix}^{n-1}\begin{bmatrix} a_{0} \\ a_{1}\end{bmatrix}$$

You might want to diagonalize the matrix $\begin{bmatrix} 0 & 1 \\ c_2 & c_1 \end{bmatrix}$.

You might want to check what is the characteristic polynomial correponding to that matrix.