¿Cómo resolver a esta relación de recurrencia? $f_n = 3f_{n-1} + 12(-1)^n$

Question

Cómo resolver esta particular relación de recurrencia ?

$$f_n = 3f_{n-1} + 12(-1)^n,\quad f_1 = 0$$

tal que $f_2 = 12, f_3 = 24$ y así sucesivamente.

He probado mucho, pero debido a $(-1)^n$ no soy capaz de resolver este recurrencia? Cualquier ayuda será muy apreciada.

Por favor, esto no es la tarea. Me encontré con este mientras que la solución de un problema en SPOJ

Answer 1

Aquí es una forma sistemática de resolver,

$$f_n - 3f_{n-1} - 12(-1)^n =0\,.$$

Cambio de $n$ en la ecuación anterior da

$$f_{n+1} - 3f_{n} + 12(-1)^n =0\,.$$

agregar las dos ecuaciones resultados en las homogénea de la ecuación de diferencia

$$f_{n+1} -2 f_{n} - 3 f_{n-1} =0$$

Ahora, podemos resolver el por encima de la recurrencia de la relación, sujeto a las condiciones iniciales $f_{0}=0$$f_2 = 12$, que es equivalente a la original. Para solucionarlo, sólo se supone que el que tiene la forma de $f_n=r^n$ y sustituya en la diferencia de la ecuación y resuelve $r$. Encontrar las raíces de las raíces del polinomio resultante en $r$ da la solución

$$f_n = c_1 (-1)^n+c_2 3^n \,.$$

La explotación de las condiciones iniciales da

$$f_n = -3 (-1)^n+ 3^{n+1} \,.$$

Answer 2

Deje $g_n=f_n-3(-1)^n$, es decir,$f_n=g_n+3(-1)^n$. Entonces $$g_n = f_n-3(-1)^n = 3f_{n-1}-3(-1)^n +12(-1)^n\\= 3g_{n-1}+9(-1)^{n-1}-3(-1)^n +12(-1)^n=3g_{n-1},$$ Por lo tanto $g_n=3^{n-1}g_1$ y, finalmente, $$f_n = 3^{n-1}g_1-3(-1)^n = 3^{n-1}(f_1+3)-3(-1)^n=3^n-3(-1)^n.$$

Answer 3

Yo no veo a nadie el uso de funciones de generación todavía, así que voy a usar de ellos por ninguna otra razón que son divertidos.

Que están tratando de resolver la recurrencia con $f_0=0$ $f_k=3f_{k-1}+12(-1)^{k+1}$ todos los $k\in\mathbb{Z}^{+}$.

Deje $F(x)=\sum_{k\geq0}f_kx^k$ ser la generación de la función de la secuencia definida por una determinada periodicidad.

$\begin{align} F(x) &= \sum_{k\geq0}f_kx^k\\ &= f_0x^0+\sum_{k\geq1}f_kx^k\\ &= \sum_{k\geq1}(3f_{k-1}+12(-1)^{k+1})x^k\\ &= \sum_{k\geq1}3f_{k-1}x^k+\sum_{k\geq1}12(-1)^{k+1}x^k\\ &= 3x\sum_{k\geq0}3f_kx^k+12x\sum_{k\geq0}(-1)^kx^k\\ &= 3xF(x)+\frac{12x}{1+x}\\ \end{align}$

Ahora podemos resolver para$F(x)$, y obtener un $F(x)=\frac{12x}{(1+x)(1-3x)}=\frac{3}{1-3x}-\frac{3}{1+x}$.

Para encontrar la forma cerrada para la recurrencia, se puede expandir $F(x)$ sobre el punto de $x_0=0$.

$\begin{align} F(x) &= \frac{3}{1-3x}-\frac{3}{1+x}\\ &= 3\sum_{k\geq0}3^kx^k-3\sum_{k\geq0}(-1)^kx^k\\ &= \sum_{k\geq0}(3^{k+1}-3(-1)^k)x^k\\ \end{align}$

Así que la forma cerrada para la recurrencia es $f_k=3^{k+1}-3(-1)^k$, para todos los no-negativo $k$.

El original de la recurrencia de utilizar un índice inicial de uno en lugar de cero. A continuación, la forma cerrada se convierte en $f_k=3^k-3(-1)^{k-1}$, para todos los positivos $k$.

EDIT: OP mencionó que él no está familiarizado con las funciones de generación, así que aquí está un enlace de la generatingfunctionology.

Answer 4

Vamos a escribir un poco más los términos de la secuencia de a, tal vez, supongo que un patrón. Va $$0, 12, 24, 84, 240, 732 \cdots$$

También tenga en cuenta que se espera que estos números a la vista algo como potencias de 3, porque eso es lo que la solución sería si no tuviéramos que $12(-1)^n$ plazo en la recurrencia. Entonces con esta sugerencia, puede ver los términos se $$3^1-3, 3^2+3, 3^3-3, 3^4+3, 3^5-3, 3^6+3 \cdots$$

así que podemos adivinar la solución es $f_n = 3^n + 3(-1)^n .$ Ahora vamos a demostrar sospechas con la inducción matemática. El caso base $n=1$ es cierto. Suponga $f_n = 3^n + 3(-1)^n$ es cierto para algunos $n.$$f_{n+1} = 3f_n - 12(-1)^n = 3( 3^n + 3(-1)^n ) - 12(-1)^n = 3^{n+1} -3(-1)^n = 3^{n+1} + 3(-1)^{n+1}$, por lo que nuestra fórmula es verdadera para $n+1$ así, completar la inducción de paso.

Answer 5

$f(1)=0$; $f(n)=3f(n-1)+12(-1)^n=3\Big(3f(n-2)+12(-1)^{n-1}\Big)+12(-1)^n$

Para $n\ge 3$

$$\begin{align*} f(n)&=3f(n-1)+12(-1)^n\\ &=3\Big(3f(n-2)+12(-1)^{n-1}\Big)+12(-1)^n\\ &=9f(n-2)+36(-1)^{n-1}+12(-1)^n\\ &=9f(n-2)+12(-1)^{n-1}\Big(3+(-1)\Big)\\ &=9f(n-2)+24(-1)^{n-1}\\ &=9f(n-2)-24(-1)^n\\ &=\begin{cases}9f(n-2)-24,&\text{if }n\text{ is even}\\ 9f(n-2)+24,&\text{if }n\text{ is odd}\;.\end{casos} \end{align*}$$

Ahora usted puede resolver por separado para el par y el impar subsecuencias.

Deje $a_0=0$$a_{n+1}=9a_n+24$$n\ge 0$. Sustituto $b_n=a_n-d$ para algunos aún desconocidos $d$, por lo que el $a_n=b_n+d$, y la repetición se convierte en $b_{n+1}+d=9(b_n+d)+24=9b_n+9d+24$ o $b_{n+1}=9b_n+8d+24$. Si establecemos $d=-3$, esto se convierte en $b_{n+1}=9b_n$, un simple exponencial de la secuencia de cuya solución tiene la forma cerrada $b_n=9^nb_0$. Y desde $b_0=a_0-(-3)=3$, nos encontramos que la forma cerrada $b_n=3\cdot9^n=3^{2n+1}$, de donde $a_n=b_n+d=3^{2n+1}-3$. Ahora verifique $f(2n+1)=a_n$, y vas a ver que $f(2n+1)=3^{2n+1}-3$. En otras palabras, $f(n)=3^n-3$ al $n$ es impar.

Usted puede manejar incluso la larga del mismo modo. Usted encontrará que $d=3$, $b_n=9^{n-1}b_1=9^n$ (desde $b_1=a_1-3=9$), y $a_n=9^n+3$. Pero $a_n=f(2n)$, lo $f(2n)=9^n+3=3^{2n}+3$, es decir, $f(n)=3^n+3$ al $n$ es incluso. La combinación de los dos, tenemos $f(n)=3^n-3(-1)^n$.