¿Cómo uno soluciona esta relación de recurrencia?

Question

Tenemos el siguiente sistema recursivo:

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

y el examen de mediados de 2005 quiere calcular la respuesta de $ \frac{a_{20}}{a_{20}+b_{20}} $.

¿Tienes alguna idea de cómo resolver esta ecuación recursiva para llegar a un valor numérico?

Answer 1

Observar que

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

y $a_0+b_0=1$, en general $a_n+b_n=2^n$.

Rápidamente calcular unos valores, vemos que el % de números $b_n$son un poco más agradable que el % de números $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{matriz} $$

Concentrarse en el $b_n$, vemos que

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

Para

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

así $a_n=2^n-n2^{n+1}=2^n(1-2n)$, y

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

(Hay otras formas de solucionar esa recurrencia de primer orden para $b_n$; Sólo elegí uno más elemental.)

Answer 2

Un truco que es norma en mi pequeño mundo es este: la matriz $$ M = \left( \begin{array}{rr} -2 & -4 \\ 4 & 6 \end{array} \right) $$ tiene traza $4$ y determinante $4.$ La característica raíces satisfacer $\lambda^2 - 4 \lambda + 4 = 0.$ El de Cayley-Hamilton Teorema (si esto no es familiar, vea el APÉNDICE) dice que $$ a_{n+2} = 4 a_{n+1} - 4 a_n, $$ $$ b_{n+2} = 4 b_{n+1} - 4 b_n. $$ Es bastante fácil para confirmar estos con cálculos directos.

Debido a las reiteradas un valor característico de a $2,$ obtenemos $a_n = A 2^n + B n 2^n,$ $b_n = C 2^n + D n 2^n.$

El cálculo de los primeros de cada uno para resolver los coeficientes, obtenemos $$ a_n = 2^n - 2n 2^n, \; \; \; \; b_n = 2n 2^n. $$

ADDENDUM:

No todo el mundo ha visto de Cayley-Hamilton. Me hizo decir que podría ser confirmada por el sencillo cálculo:

Supongamos que tenemos el sistema $$ \color{blue}{ a_{n+1} = \alpha a_n + \beta b_n,}$$ $$ \color{blue}{ b_{n+1} = \gamma a_n + \delta b_n.} $$

Encontraremos $a_{n+2}$ en dos formas ligeramente diferentes.

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

Déjame ir directamente a este, definir $$ \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. $$ De $$ a_{n+2} = (\alpha^2 + \beta \gamma) a_n +(\alpha \beta + \beta \delta) b_n $$ nos encontramos $$ a_{n+2} = \Psi, $$ o $$ \color{blue}{ a_{n+2} = (\alpha + \delta) a_{n+1} - (\alpha \delta - \beta \gamma) a_n.} $$ Un análogo de cálculo de works para $b_{n+2}= (\alpha + \delta) b_{n+1} - (\alpha \delta - \beta \gamma) b_n .$

Answer 3

Sumando las dos ecuaciones obtienes

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

para que $a_n+b_n=2^{n}$.

Tapar esto en la primera ecuación obtiene $$ a_ {n + 1} = −4(a_n+b_n) + 2a_n =-4\cdot2 ^ n + 2a_n, $$ que es, dividiendo en $2^{n+1}$ $ {a_ {n + 1} \over 2 ^ {n+1}} =-2 + {a_n\over2 ^ n}. $$ Sigue que $a_n/2^n$ es una progresión aritmética y $ {a_n\over2 ^ n} =-2n + 1. $$

Answer 4

Podemos escribir a la relación de recurrencia en forma de matriz

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

Por lo tanto,

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

Desafortunadamente, la matriz no es diagonalizable. Nos da su descomposición de Jordania

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

Por lo tanto,

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