Resuelve la relación de recurrencia $a_n = 5a_{n-1}-8a_{n-2}+4a_{n-3}$ y $a_0 = 0$, $a_1 = 0$, $a_2 = 1$.

Question

Considera la relación de recurrencia $a_n = 5a_{n-1}-8a_{n-2}+4a_{n-3}$ y $a_0 = 0$, $a_1 = 0$, $a_2 = 1$. Encuentra una expresión en forma cerrada para $a_n$.

He calculado la Función Generatriz Ordinaria $A(z)$ de $(a_n)_n$ como

$$A(z) = \frac{z^2}{1-5z+8z^2-4z^3}.$$

Según Wolfram Alpha esto tiene la siguiente descomposición en fracciones parciales:

$$= \frac{-3}{2(1-2z)} + \frac{1}{2(1-2z)^2} + \frac{1}{1-z}$$

y usando el Teorema Binomial Generalizado obtenemos:

$$= -\frac{3}{2} \sum_{n = 0}^\infty 2^nz^n + \frac{1}{2} \sum_{n=0}^\infty \binom{-2}{n}2^nz^n + \sum_{n=0}^\infty z^n.$$

Por lo tanto, deberíamos tener

$$a_n = [z^n]A(z) = -\frac{3}{2}2^n + \frac{1}{2} \binom{-2}{n}2^n +1 = -3 \cdot 2^{n-1} + \binom{-2}{n}2^{n-1} +1 $$

Sin embargo, esto no parece ser cierto. ¿Podrías decirme por favor qué estoy haciendo mal?

Answer 1

De Wolfram Alpha

Wolfram Alpha

Answer 2

La ecuación característica es $r^3-5r^2+8r-4=(r-1)(r-2)^2$

Así que $a_n=a\,1^n+(bn+c)\,2^n$

Aplicando las condiciones iniciales tenemos $\begin{cases}a_0=a+c=0\\a_1=a+2(b+c)=0\\a_2=a+4(2b+c)=1\end{cases}\iff a=1,\ c=-1,\ b=\frac 12$

$$a_n=2^n(\tfrac n2-1)+1$$

Answer 3

Comenzando desde $$\frac{z^2}{1-5z+8z^2-4z^3}$$ entonces \begin{align} \sum_{n=0}^{\infty} a_{n} \, x^n &= \frac{x^2}{1-5x+8x^2-4x^3} = \frac{x^2}{(1-x)(1-2 x)^2} \\ &= \frac{1}{1 - x} - \frac{3}{2 (1 - 2 x)} + \frac{1}{2 \, (1 - 2 x)^2} \\ &= \sum_{n} x^n - \frac{3}{2} \, \sum_{n} 2^n \, x^n + \frac{1}{2} \, \sum_{n} 2^n (n+1) \, x^n \\ &= \sum_{n=0}^{\infty} \left(1 - 3 \cdot 2^{n-1} + 2^{n-1} \, (n+1) \right) \, x^n \\ &= \sum_{n=0}^{\infty} \left(1 + 2^{n-1} \, (n-2) \right) \, x^n \end{align} lo cual resulta en $$ a_{n} = 1 + 2^{n-1} \, (n-2). $$

Como verificación: \begin{align} \phi_{n} &= 5 \, a_{n-1} - 8 \, a_{n-2} + 4 \, a_{n-3} \\ &= (5 - 8 + 4) + 2^{n-4} \, (5 \cdot 4 \, (n-3) - 8 \cdot 2 \, (n-4) + 4 \, (n-5)) \\ &= 1 + 2^{n-1} \, (n-2) = a_{n} \end{align} lo cual es el resultado esperado.