Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
Nice compact but complete description. – André Nicolas Oct 6 '12 at 17:26

$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}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.