# How does one solve this recurrence relation? [closed]

We have the following recursive system:

$$\begin{cases} & a_{n+1}=-2a_n -4b_n\\ & b_{n+1}=4a_n +6b_n\\ & a_0=1, b_0=0 \end{cases}$$

and the 2005 mid-exam wants me to calculate answer of $\frac{a_{20}}{a_{20}+b_{20}}$.

Do you have any idea how to solve this recursive equation to reach a numerical value?

## closed as off-topic by Did, choco_addicted, JMP, user175968, NikunjMay 21 '16 at 6:49

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Did, choco_addicted, JMP, Community, Nikunj
If this question can be reworded to fit the rules in the help center, please edit the question.

• I suppose you're asking because you want an answer other than just crunching the numbers from 0 to 20. But if you really only needed the 20th elements, that's what I would do. – Owen May 16 '16 at 20:15

Observe that

$$a_{n+1}+b_{n+1}=2a_n+2b_n=2(a_n+b_n)\;,$$

and $a_0+b_0=1$, so in general $a_n+b_n=2^n$.

Quickly calculating a few values, we see that the numbers $b_n$ are a little nicer than the numbers $a_n$:

$$\begin{array}{rcc} n:&0&1&2&3&4\\ a_n:&1&-2&-12&-40&-112\\ b_n:&0&4&16&48&128\\ \end{array}$$

Concentrating on the $b_n$, we see that

$$b_{n+1}=4(a_n+b_n)+2b_n=2^{n+2}+2b_n\;,$$

so that

\begin{align*} b_n&=2b_{n-1}+2^{n+1}\\ &=2(2b_{n-2}+2^n)+2^{n+1}\\ &=2^2b_{n-2}+2\cdot2^{n+1}\\ &=2^2(2b_{n-3}+2^{n-1})+2\cdot 2^{n+1}\\ &=2^3b_{n-3}+3\cdot 2^{n+1}\\ &\;\;\vdots\\ &=2^kb_{n-k}+k2^{n+1}\\ &\;\;\vdots\\ &=2^nb_0+n2^{n+1}\\ &=n2^{n+1}\;, \end{align*}

so $a_n=2^n-n2^{n+1}=2^n(1-2n)$, and

$$\frac{a_n}{a_n+b_n}=\frac{2^n(1-2n)}{2^n}=1-2n\;.$$

(There are other ways to solve that first-order recurrence for $b_n$; I just picked the most elementary one.)

• Very nice but the answer sheet says -39 not -18 !! – Maryam Koj May 15 '16 at 22:21
• @Maryam: Sorry: I made a silly algebra error in the simplification of $a_n$. It’s fixed now. – Brian M. Scott May 15 '16 at 22:28

A trick that is standard in my little world is this: the matrix $$M = \left( \begin{array}{rr} -2 & -4 \\ 4 & 6 \end{array} \right)$$ has trace $4$ and determinant $4.$ The characteristic roots satisfy $\lambda^2 - 4 \lambda + 4 = 0.$ The Cayley-Hamilton Theorem (if this is not familiar, see the ADDENDUM) says that $$a_{n+2} = 4 a_{n+1} - 4 a_n,$$ $$b_{n+2} = 4 b_{n+1} - 4 b_n.$$ It is easy enough to confirm these with direct calculations.

Because of the repeated characteristic value $2,$ we get $a_n = A 2^n + B n 2^n,$ with $b_n = C 2^n + D n 2^n.$

Calculating the first few of each to solve for the coefficients, we get $$a_n = 2^n - 2n 2^n, \; \; \; \; b_n = 2n 2^n.$$

Not everyone has seen Cayley-Hamilton. I did say it could be confirmed by straightforward calculation:

Suppose we have the system $$\color{blue}{ a_{n+1} = \alpha a_n + \beta b_n,}$$ $$\color{blue}{ b_{n+1} = \gamma a_n + \delta b_n.}$$

We will find $a_{n+2}$ in two slightly different ways.

$$a_{n+2} = \alpha a_{n +1} + \beta b_{n +1} = \alpha(\alpha a_n + \beta b_n) + \beta ( \gamma a_n + \delta b_n) = (\alpha^2 + \beta \gamma) a_n +(\alpha \beta + \beta \delta) b_n$$

Let me go straight to this, define $$\Psi = (\alpha + \delta) a_{n+1} - (\alpha \delta - \beta \gamma) a_n,$$ $$\Psi = (\alpha + \delta)( \alpha a_n + \beta b_n) - (\alpha \delta - \beta \gamma) a_n,$$ $$\Psi = (\alpha^2 + \alpha \delta) a_n + (\alpha \beta + \beta \delta)b_n - (\alpha \delta - \beta \gamma) a_n,$$ $$\Psi = (\alpha^2 + \beta \gamma) a_n + (\alpha \beta + \beta \delta)b_n.$$ From $$a_{n+2} = (\alpha^2 + \beta \gamma) a_n +(\alpha \beta + \beta \delta) b_n$$ we find $$a_{n+2} = \Psi,$$ or $$\color{blue}{ a_{n+2} = (\alpha + \delta) a_{n+1} - (\alpha \delta - \beta \gamma) a_n.}$$ An analogous calculation works for $b_{n+2}= (\alpha + \delta) b_{n+1} - (\alpha \delta - \beta \gamma) b_n .$

By adding the two equations you get

$a_{n+1}+b_{n+1}=2(a_n+b_n)$,

so that $a_n+b_n=2^{n}$.

Plugging this into the first equation one gets $$a_{n+1}=−4(a_n+b_n)+2a_n=-4\cdot2^n+2a_n,$$ that is, dividing by $2^{n+1}$ $${a_{n+1}\over 2^{n+1}}=-2+{a_n\over2^n}.$$ It follows that $a_n/2^n$ is an arithmetic progression and $${a_n\over2^n}=-2n+1.$$

• Thanks but I have the final solution. is it possible add more detail ? – Maryam Koj May 15 '16 at 21:54
• I've added some details. I think you can go on by yourself now. – Aretino May 15 '16 at 22:00
• Sorry, you are right. this is a simple case. but maybe add how you reach to second equation? (so that...). infact my problem via things that obvious to you not me. if i didnt waste your time please explain more for me. – Maryam Koj May 15 '16 at 22:05
• Shouldn't it be $a_n + b_n = 2^n$? – TastyRomeo May 15 '16 at 22:07
• @SteamyRoot Do one iteration with the boundary condition given and you will see why the exponent is $n-1$. – GFauxPas May 15 '16 at 22:19

We can write the recurrence relation in matrix form

$$\begin{bmatrix} a_{k+1}\\ b_{k+1}\end{bmatrix} = \begin{bmatrix}-2 & -4\\ 4 & 6\end{bmatrix} \begin{bmatrix} a_{k}\\ b_{k}\end{bmatrix}$$

Hence,

$$\begin{bmatrix} a_{n}\\ b_{n}\end{bmatrix} = \begin{bmatrix}-2 & -4\\ 4 & 6\end{bmatrix}^n \begin{bmatrix} a_{0}\\ b_{0}\end{bmatrix}$$

Unfortunately, the matrix is not diagonalizable. Its Jordan decomposition gives us

$$\begin{array}{rl}\begin{bmatrix} a_{n}\\ b_{n}\end{bmatrix} &= \begin{bmatrix}-1 & \frac{1}{4}\\ 1 & 0\end{bmatrix} \begin{bmatrix} 2 & 1\\ 0 & 2\end{bmatrix}^n \begin{bmatrix} 0 & 1\\ 4 & 4\end{bmatrix} \begin{bmatrix} a_{0}\\ b_{0}\end{bmatrix}\\\\ &= \begin{bmatrix}-1 & \frac{1}{4}\\ 1 & 0\end{bmatrix} \begin{bmatrix} 2^n & n \, 2^{n-1}\\ 0 & 2^n\end{bmatrix} \begin{bmatrix} b_{0}\\ 4 a_{0} + 4 b_{0}\end{bmatrix}\\\\ &= \begin{bmatrix} -2^n & (1 - 2n) \, 2^{n-2}\\ 2^n & n \, 2^{n-1}\end{bmatrix} \begin{bmatrix} b_{0}\\ 4 a_{0} + 4 b_{0}\end{bmatrix}\end{array}$$

If $a_0 = 1$, $b_0 = 0$ and $n = 20$,

$$\begin{bmatrix} a_{20}\\ b_{20}\end{bmatrix} = \begin{bmatrix} -2^{20} & -39 \cdot 2^{18}\\ 2^{20} & 20 \cdot 2^{19}\end{bmatrix} \begin{bmatrix} 0\\ 2^2\end{bmatrix} = 2^{20} \begin{bmatrix} -39\\ 40\end{bmatrix}$$

Thus,

$$\dfrac{a_{20}}{a_{20} + b_{20}} = \dfrac{-39}{-39 + 40} = -39$$

• This is sorta kinda equivalent to Will's answer, methinks. – J. M. is a poor mathematician May 16 '16 at 16:27
• Okay. Your answer came at 00:18, Zulu time. Will's answer is at 22:58, slightly more than an hour earlier if I reckoned correctly. Which then makes me ask, what about the timestamps did you want me to look at? – J. M. is a poor mathematician May 16 '16 at 16:34
• I didn't say you were plagiarizing. I said that this is equivalent. You are trying to read a moral judgment in my observation, where there isn't any. – J. M. is a poor mathematician May 16 '16 at 16:38
• *sigh* the defensiveness really is unwarranted. In any case, look at the result of taking the power of a Jordan block, and compare with the ansatz Will got through CH. Anyway, sorry for ruffling your feathers, but we should probably cut this discussion short. – J. M. is a poor mathematician May 16 '16 at 16:50
• Yes, it is equivalent in that sense. – Rodrigo de Azevedo May 16 '16 at 16:52