Solving a mathematical recursion to find explicit function

Question

I came across the recursive sequence

$$ \begin{align} a_{n+1}&=(r-2)a_n+(r-1)b_n\;,\\ b_{n+1}&=a_n\;, \end{align} $$

and the explicit formula

$$ a_n=(-1)^n(r-1)+(r-1)^n\;. $$

I saw that it is solved using a standard technique, finding roots to the characteristic equation, in this case $$ \lambda^2-(r-2)\lambda-(r-1)=0\;, $$ and then putting them in the

$$ a_n=c_1(\lambda_1)^n+c_2(\lambda_2)^n\;, $$

I wanted to know a proof or derivation for this method. How anyone arrived at such a solution. What is the methodology?

Any help appreciated!

Answer 1

First of all, it is easy to check by induction that it works if you follow these steps. However, I assume you would also like to know how one would come up with this idea in a more "systematic way". You can rewrite your recursive equations in matrix notation as $$\begin{bmatrix} a_{n+1} \\ b_{n+1} \end{bmatrix} = \begin{bmatrix} r-2 & r-1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_n \\ b_n \end{bmatrix}.$$ Denoting the matrix by $A$, the characteristic equation gives the eigenvalues $\lambda_1$ and $\lambda_2$ of $A$ as roots. Assuming that they are different, the matrix $A$ can be diagonalized as $A=BDB^{-1}$ with $D$ being the diagonal matrix with entries $\lambda_1$ and $\lambda_2$, and the columns of $B$ being eigenvectors for $\lambda_1$ and $\lambda_2$, respectively. Then $$\begin{bmatrix} a_n \\ b_n \end{bmatrix} = B \begin{bmatrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{bmatrix} B^{-1} \begin{bmatrix} a_0 \\ b_0 \end{bmatrix}.$$ Now you can either compute $B$ and $B^{-1}$ explicitly by finding the eigenvectors of $A$, or you can infer from this equation that both $a_n$ and $b_n$ are linear combinations of $\lambda_1^n$ and $\lambda_2^n$, with coefficients independent of $n$, and find those coefficients ($c_1$ and $c_2$ in your notation) by using the initial values for the recursion.

Answer 2

$a_{n+1}=(r-2)a_{n}+(r-1)b_{n}$ and $b_{n+1}=a_{n}$ means that $a_{n+1}=(r-2)a_{n}+(r-1)a_{n-1}$ or $a_{n+1}-(r-2)a_{n}-(r-1)a_{n-1}=0$, it's character equation is $\lambda^2-(r-2)\lambda-(r-1)=0$.

More generally, character equation of type as $a_{n+1}+k_{1}a_{n}+k_{2}a_{n-1}=0$ is $\lambda^2+k_{1}\lambda+k_{2}=0$, if the two roots are $\lambda_{1}$ and $\lambda_{2}$, then $-k_{1}=\lambda_{1}+\lambda_{2}$ and $k_{2}=\lambda_{1}\lambda_{2}$.

Then the original equation is $a_{n+1}-(\lambda_{1}+\lambda_{2})a_{n}+\lambda_{1}\lambda_{2}a_{n-1}=0$, so we have

$$\begin{align} a_{n+1}-\lambda_{1}a_{n}&=\lambda_{2}(a_{n}-\lambda_{1}a_{n-1})\\ a_{n}-\lambda_{1}a_{n-1}&=\lambda_{2}(a_{n-1}-\lambda_{1}a_{n-2})\\ &\vdots\\ a_{3}-\lambda_{1}a_{2}&=\lambda_{2}(a_{2}-\lambda_{1}a_{1}) \end{align}$$

So we have $a_{n+1}-\lambda_{1}a_{n}=\lambda_{2}^{n-1}(a_{2}-\lambda_{1}a_{1})$, we can denote it as $a_{n+1}-\lambda_{1}a_{n}=d_{1}\lambda_{2}^{n}$.

Similarly, we can get $a_{n+1}-\lambda_{2}a_{n}=d_{2}\lambda_{1}^{n}$.

Consider above two equalities, by calculation, we can get $a_{n}$ have the form $$a_n=c_{1}\lambda_{1}^{n}+c_{2}\lambda_{2}^{n}$$