Resolución lineal de la ecuación recursiva $a_n = a_{n-1} + 2 a_{n-2} + 2^n$.

Question

Quiero resolver el lineal de la ecuación recursiva:

$a_n = a_{n-1} + 2a_{n-2} + 2^n$, donde $a_0 = 2$, $a_1 = 1$.

He intentado usar el Ansatz método y la generación de la función de método de la siguiente manera:

Ansatz método

En primer lugar, por la parte homogénea, $a_n = a_{n-1} + 2a_{n-2}$, supongo que $a_n = \lambda^n$ como la solución, y sustituyendo y resolviendo la ecuación cuadrática, llego $\lambda = -1, 2$. Por eso, $a_n = \alpha (-1)^n + \beta 2^n$. Entonces, para el inhomogenous parte, supongo que $a_n = \gamma 2^n$, para obtener el $\gamma 2^n = \gamma 2^{n-1} + 2\gamma 2^{n-2} + 2^n$, de donde $2^n=0$, lo que significa, supongo, que esta conjetura no es válido. Estos son el tipo de conjeturas que suelen trabajar, así que no sé por qué no funciona en este caso en particular, y qué hacer de otra manera, así que he intentado que la generación de la función de método.

La generación de la función de método

Vamos $$ A(z) = \sum_{i=0}^{\infty} a_k z^k $$ ser la generación de la función de la secuencia de $\{ a_n \}_{n \in \mathbb{N} \cup {0}}$. Entonces, trato de escribir la relación recursiva en términos de $A(z)$: $$ A(z) = zA(z) + 2z^2(z) + \frac{1}{1-2z} + (1 - 2z), $$ donde el último término entre corchetes surge a causa de las condiciones iniciales. Entonces, la solución para $A(z)$, $$ \begin{align} A(z) &= \frac{1}{(1+z)(1-2z)^2} + \frac{1}{1+z}\\ &= \frac{2}{9}\frac{1}{1-2z} + \frac{2}{3}\frac{1}{(1-2z)^2} + \frac{10}{9}\frac{1}{1+z}\\ &=\frac{2}{9} \sum_{k=0}^{\infty} 2^k z^k + \frac{2}{3} \sum_{k=0}^{\infty} (k+1)2^k z^k + \frac{10}{9} \sum_{k=0}^{\infty} (-1)^k z^k\\ &= \sum_{k=0}^\infty \frac{(3k+4)2^{k+1} + (-1)^k 10}{9} z^k. \end{align} $$ Así, $$ a_k = \frac{(3k+4)2^{k+1} + (-1)^k 10}{9}. $$ Pero entonces, $a_1 = 2$, mientras que empezamos con $a_1 = 1$.

Al principio, pensé que tal vez la generación de la función de método no funcionó debido a que algunas de las series en el lado derecho no eran convergentes, pero todos ellos parecen estar convergiendo para $|z| < 1/2$. He revisado mis cálculos varias veces, así que no creo que haya ningún error simple como eso. Sería genial si alguien me explicara exactamente qué está pasando mal aquí.

Answer 1

El $1-2z$ en su implícita de la ecuación de $A(z)$ no es correcta, debería ser $1-3z$:

$$\begin{eqnarray*}A(z)&=& a_0 + a_1 z + \sum_{n \geq 2} a_n z^n \\ &=& 2+ z + \sum_{n \geq 2} a_{n-1} z^n + \sum_{n \geq 2} 2 a_{n-2} z^n + \sum_{n \geq 2} 2^n z^n \\ &=&2+ z + \sum_{n \geq 1} a_n z^{z+1} + \sum_{n \geq 0} 2 a_n z^{n+2} + \sum_{n \geq 2} (2z)^n \\ &=&2+ z + \bigl(z A(z)-2 z\bigr) + 2 z^2 A(z) + \left(\frac{1}{1-2z}-1-2z\right)\\ &=&1-\color{red}{3} z + z A(z) + 2z^2 A(z) + \frac{1}{1-2z}\end{eqnarray*}$$ Ahora usted puede utilizar su método para calcular los coeficientes de $A(z)$. Esto se hace en detalle en Brian M. Scott respuesta.

Answer 2

Supongamos que $$ a_n=a_{n-1}+2a_{n-2}+2^n\etiqueta{1} $$ Deje $a_n=b_n+\frac23n\,2^n$, luego $$ b_n+\frac23n\,2^n =b_{n-1}+\frac23(n-1)\,2^{n-1}+2b_{n-2}+2\cdot\frac23(n-2)\,2^{n-2}+2^n\etiqueta{2} $$ y cancelación, obtenemos $$ b_n=b_{n-1}+2b_{n-2}\etiqueta{3} $$ La solución estándar a$(3)$$b_n=c_1(-1)^n+c_22^n$. Por lo tanto, $$ a_n=c_1(-1)^n+\left(c_2+\frac23n\right)2^n\etiqueta{4} $$ La solución para $a_0=2$$a_1=1$, obtenemos $$ a_n=\frac{13}9(-1)^n+\left(\frac59+\frac23n\right)2^n\etiqueta{5} $$

---

Comentarios sobre el Ansatz Método

Deje $Sa_n=a_{n+1}$. Si aplicamos $S-2$$(1)$, obtenemos $$ \begin{align} (S-2)\left(a_n-a_{n-1}-2a_{n-2}\right) &=(S-2)2^n\\ &=0\tag{6} \end{align} $$ Esto significa $$ (S+1)(S-2)^2a_n=0\etiqueta{7} $$ El problema con el Ansatz método, es el exponente de $2$$(S-2)$.

La solución estándar para $(7)$$a_n=c_1(-1)^n+(c_2+c_3n)2^n$.

Answer 3

Utilizando la ecuación característica del método, tenemos la parte homogénea de la ecuación dada, $$g_n = g_{n-1} + 2g_{n-2}$$ Como lo han hecho, las raíces de la ecuación característica son $2$$-1$, por lo que la solución a la parte homogénea es $c_12^n + c_2(-1)^n$ para algunas constantes $c_1$$c_2$. Para las no homogéneas parte, de acuerdo con el comentario de @AndreNicolas, podemos suponer que la solución es de la forma $c_3n2^n$ y podemos escribir: $$c_3n2^n = c_3(n-1)2^{n-1} + 2c_3(n-2)2^{n-2} + 2^n \\ \implica c_3 = \frac{2}{3}$$

Nota: suponemos $c_3n2^n$ para las no homogéneas, y no $c_32^n$, debido a $2$ ya es una raíz de la ecuación característica de la parte homogénea. De la misma manera, cuando nos han repetido las raíces de la parte homogénea (dicen que la raíz de $a$ aparece tres veces), utilizamos $c_1a^n + c_2na^n + c_3n^2a^n$, etc.

Ahora, $$\begin{align} a_n &= h_n + n\frac{2 \cdot 2^n}{3} \\ &= c_12^n + c_2(-1)^n + \frac{2^{n+1}n}{3} \end{align}$$ y sustituyendo a $a_0$$a_1$, obtenemos $c_1 = \frac{5}{9}$, $c_2 = \frac{13}{9}$, y $$a_n = \frac{5\cdot 2^n}{9} + \frac{13 \cdot (-1)^n}{9} + \frac{2^{n+1}n}{3}$$

Answer 4

Voy a usar las funciones de generación. Yo primero reescribir la recurrencia de manera que se tiene para todos los $n\ge 0$ en el supuesto de que $a_n=0$$n<0$:

$$a_n=a_{n-1}+2a_{n-2}+2^n+[n=0]-3[n=1]\;,\tag{1}$$

donde los dos últimos términos de uso de la Iverson soporte. (Esto es básicamente una manera disimulada de cuidar de los valores iniciales derecho desde el inicio). Ahora multiplique $(1)$ $x^n$ y suma más de $n\ge 0$, escribir $A(x)$$\sum_{n\ge 0}a_nx^n$:

$$\begin{align*} A(x)&=\sum_{n\ge 0}a_{n-1}x^n+2\sum_{n\ge 0}a_{n-2}x^n+\sum_{n\ge 0}2^nx^n+1-3x\\ &=x\sum_{n\ge 0}a_{n-1}x^{n-1}+2x^2\sum_{n\ge 0}a_{n-2}x^{n-2}+\frac1{1-2x}+1-3x\\ &=xA(x)+2x^2A(x)+\frac{2-5x+6x^2}{1-2x}\;, \end{align*}$$

así

$$A(x)=\frac{2-5x+6x^2}{(1-2x)(1-x-2x^2)}=\frac{2-5x+6x^2}{(1-2x)^2(1+x)}\;.$$

Dividir esto en fracciones parciales:

$$\frac{2-5x+6x^2}{(1+x)(1-2x)^2}=\frac{a}{1+x}+\frac{b}{1-2x}+\frac{c}{(1-2x)^2}\;,$$

así

$$2-5x+6x^2=a(1-2x)^2+b(1+x)(1-2x)+c(1+x)\;.$$

Sustituyendo $x=\frac12$, nos encontramos con que $\frac32c=1$ o $c=\frac23$. Sustituyendo $x=-1$, encontramos que del mismo modo que $9a=13$ o $a=\frac{13}9$. Por lo tanto,

$$\begin{align*} 2-5x+6x^2&=\frac{13}9(1-2x)^2+b(1+x)(1-2x)+\frac23(1+x)\\ &=\left(\frac{13}9+b+\frac23\right)+x\left(-\frac{52}9-b+\frac23\right)+x^2\left(\frac{52}9-2b\right)\\ &=\left(b+\frac{19}9\right)+x\left(-b-\frac{46}9\right)+x^2\left(\frac{52}9-2b\right)\;, \end{align*}$$

por lo $b+\frac{19}9=2$, e $b=-\frac19$. Como una comprobación de seguridad se comprueba fácilmente que los otros dos coeficientes de producir el mismo valor de $b$, por lo que

$$\begin{align*} A(x)&=\frac19\left(\frac{13}{1+x}-\frac1{1-2x}+\frac6{(1-2x)^2}\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+3\cdot\frac2{(1-2x)^2}\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+3\cdot\frac{d}{dx}\left(\frac1{1-2x}\right)\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+3\sum_{n\ge 0}n2^nx^{n-1}\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+6\sum_{n\ge 0}(n+1)2^nx^n\right)\\ &=\sum_{n\ge 0}\frac{13(-1)^n-2^n+6(n+1)2^n}9x^n\\ &=\sum_{n\ge 0}\frac{(6n+5)2^n+13(-1)^n}9x^n\;, \end{align*}$$

y

$$a_n=\frac{(6n+5)2^n+13(-1)^n}9\;.$$