Demostración de la forma cerrada de la secuencia definida recursivamente

Question

Sea $f:\mathbb{N} \rightarrow \mathbb{N}$ se define por $f(1) = 5, f(2) = 13$ y para $n \ge 2, f(n) = 2f(n - 2) + f(n - 1)$ . Demostrar que $f(n) = 3\cdot 2^n + (-1)^n$ para todos $n \in N$

Hasta ahora he demostrado que $f(n)$ es verdadera cuando $n = 1, 2$ . Para $k \ge 3$ supongamos que $p(j)$ es cierto para todos $j \in N, j < k$

Ahora quiero demostrar que $p(k)$ es cierto para todos $k \in N$

¿Cómo lo haría?

Answer 1

Hagamos una inducción sobre $n$ .

• Arranque por inducción. $f(1)=5=3\cdot 2-1$ y $f(2)=13=3\cdot 4+1$ (nótese que realmente necesitamos el primer dos en el inicio de la inducción, porque la recurrencia utiliza los dos valores anteriores).

• Hipótesis de inducción. Para algunos $n\ge 1$ suponemos que hemos demostrado la fórmula para todos los $k\le n$ .

• Paso de inducción. Demostramos que la fórmula también es válida para $n+1\ge 2$ :

$$f(n+1)=2f(n-1)+f(n)=2\cdot (3\cdot 2^{n-1}+(-1)^{n-1})+3\cdot 2^n + (-1)^n=3\cdot 2^{n+1}+(-1)^{n+1}$$

Answer 2

Sugerencia: Pruebe la inducción. Suponga que la afirmación es válida para $n$ y a partir de ahí, demostrar que vale para $n+1$ .

Answer 3

Sugerencia $\ $ Sea $\,S g(n) = g(n\!+\!1)$ sea el operador de desplazamiento. $(S-2)(2^n) = 0 = (S+1)(-1^n)$ por lo que su producto $(S-2)(S+1) = S^2\!-S-2$ mata $\, f_n = c\,2^n + d (-1)^n\,$ para cualquier $\,c,d\,$ independiente de $\,n.$ Por lo tanto, deducimos $\, 0 = (S^2\!-S-2)f_n = f_{n+2} - f_{n} - 2f_n,\ $ Es decir $\ f_{n+2} = f_{n+1} + 2 f_n.$

Observación $\ $ Véase esta respuesta para ver otro ejemplo y una explicación más detallada. Esto explica cómo funciona la prueba en la respuesta de TooOldForMath.