¿Cómo puedo resolver la relación de recurrencia [matemática] F (n) = F (n-1) + 2F (n-2) [/ matemática] dada la siguiente función por partes: F (n) = 1, n = 1 F (n) = 5, n = 2 F (n) = F (n-1) + 2F (n-2), n> = 3?

Sé que esta es una vieja pregunta, pero quería responderla de una manera muy diferente, para que las personas puedan notar cómo se pueden usar las series de poder formales para resolver tales problemas.

Deje [math] F (n + 1) = a_n [/ math]. Empezamos desde

[matemáticas] a_n = a_ {n-1} + 2a_ {n-2}. [/ matemáticas]

[matemáticas] a_nx ^ n = a_ {n-1} x ^ n + 2a_ {n-2} x ^ n. [/ matemáticas]

[matemáticas] \ displaystyle \ sum_ {n = 2} ^ \ infty a_nx ^ n = \ sum_ {n = 2} ^ \ infty a_ {n-1} x ^ n + 2 \ sum_ {n = 2} ^ \ infty a_ {n-2} x ^ n. \ qquad [*] [/ math]

Aquí, [math] \ displaystyle \ sum_ {n = 0} ^ \ infty a_nx ^ n [/ math] es una serie de poder formal. Piense en una serie de poder formal como una serie de poder donde nunca consideramos ‘sustituir valores por [math] x [/ math]’. En consecuencia, no tenemos preguntas de convergencia que hacer. Las series de potencias formales forman un anillo bajo las operaciones habituales de suma y multiplicación de series de potencia.

Volviendo a [matemáticas] [*] [/ matemáticas], tenemos

[matemáticas] \ displaystyle \ left (\ sum_ {n = 0} ^ \ infty a_nx ^ n \ right) -a_0-a_1x = x \ left (\ left (\ sum_ {n = 0} ^ \ infty a_nx ^ n \ right) -a_0 \ right) + 2x ^ 2 \ left (\ sum_ {n = 0} ^ \ infty a_nx ^ n \ right) [/ math]

[matemáticas] \ displaystyle (1-x-2x ^ 2) \ left (\ sum_ {n = 0} ^ \ infty a_nx ^ n \ right) = a_0 + a_1x-a_0x [/ math]

[matemáticas] \ displaystyle \ sum_ {n = 0} ^ \ infty a_nx ^ n = \ dfrac {a_0 (1-x) + a_1x} {1-x-2x ^ 2}. [/ math]

Como se nos da que [matemáticas] a_0 = 1 [/ matemáticas] y [matemáticas] a_1 = 5 [/ matemáticas], tenemos

[matemáticas] \ displaystyle \ sum_ {n = 0} ^ \ infty a_nx ^ n = \ dfrac {1 + 4x} {1-x-2x ^ 2}. [/ math]

Ahora tenga en cuenta que

[matemáticas] \ dfrac {1 + 4x} {1-x-2x ^ 2} = \ dfrac {2} {1-2x} – \ dfrac {1} {1 + x} [/ matemáticas]

utilizando técnicas habituales de fracciones parciales. Además,

[matemáticas] (1-2x) (1 + 2x + 4x ^ 2 + 8x ^ 3 + \ cdots) = (1 + 2x + 4x ^ 2 + 8x ^ 3 + \ cdots) + (- 2x-4x ^ 2- 8x ^ 3- \ cdots) = 1 [/ matemáticas]

y

[matemáticas] (1 + x) (1-x + x ^ 2-x ^ 3 + \ cdots) = (1-x + x ^ 2-x ^ 3 + \ cdots) + (xx ^ 2 + x ^ 3 – \ cdots) = 1. [/ math]

Por lo tanto

[matemáticas] \ displaystyle \ sum_ {n = 0} ^ \ infty a_nx ^ n = 2 (1 + 2x + 4x ^ 2 + 8x ^ 3 + \ cdots) + (- 1 + xx ^ 2 + x ^ 3 + \ cdots) [/ math]

[matemáticas] \ displaystyle \ sum_ {n = 0} ^ \ infty a_nx ^ n = \ sum_ {n = 0} ^ \ infty (2 ^ {n + 1} + (- 1) ^ {n + 1}) x ^ n. [/ matemáticas]

Así [matemáticas] a_n = 2 ^ {n + 1} + (- 1) ^ {n + 1} [/ matemáticas], entonces [matemáticas] F_n = 2 ^ n + (- 1) ^ n [/ matemáticas].

[matemáticas] F (n) = F (n-1) + 2 * F (n-2) [/ matemáticas]
[matemáticas] F (5) = 2 [/ matemáticas]
[matemáticas] F (1) = 1 [/ matemáticas]

Método lineal (ver fuente):
El polinomio característico de esta recurrencia es:
[matemáticas] r ^ 2 = r + 2 [/ matemáticas]
Las raíces / valores de r que satisfacen esto son:
[matemáticas] r_1 = -1 [/ matemáticas] y [matemáticas] r_2 = 2 [/ matemáticas]

La solución a la recurrencia está en el formulario:
[matemáticas] F (n) = c_1 * r_1 ^ n + c_2 * r_2 ^ n [/ matemáticas]
Las constantes [matemáticas] c_1 [/ matemáticas] y [matemáticas] c_2 [/ matemáticas] se encuentran utilizando las condiciones F (5) = 2 y F (1) = 1.
Obtenemos [matemáticas] c_1 = c_2 = 1 [/ matemáticas].

Por lo tanto, [matemáticas] F (n) = (-1) ^ n + 2 ^ n [/ matemáticas]

Cómo resolver relaciones recurrentes