# 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?

• 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