How does one solve this recurrence relation?

Question

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?

Answer 1

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.)

Answer 2

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

Answer 3

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

ADDENDUM:

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

Answer 4

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