Recurrencias

[Ivan]

Una recurrencia lineal de grado [math]k es una sucesión definida del siguiente modo:

• Se define arbitrariamente para [math]A_i ([math]0\leq i\leq k-1)
• Si [math]n\geq k entonces [math]\displaystyle A_n=\sum_{i=1}^{k} c_{k-i}A_{n-i} (los [math]c_j son números fijos).

Por ejemplo Fibonacci es una recurrencia lineal de grado [math]2:

• [math]F_0=0
• [math]F_1=1
• [math]F_n=F_{n-1}+F_{n-2}

La idea es encontrar una forma general de resolver recurrencias lineales, o sea de encontrar una fórmula.

[Ivan]

Primero vamos a resolver Fibonacci. La idea es encontrar dos secuencias de la forma [math]K^n que verifiquen [math]F_n=F_{n-1}+F_{n-2} (con [math]K no nulo. O sea queremos que valga:

[math]\displaystyle{K^n=K^{n-1}+K^{n-2}}

Pero entonces podemos dividir por [math]K^{n-2} y obtenemos [math]K^2=K+1. Entonces [math]K es raíz de esa ecuación. Reciprocamente si [math]K es raíz la secuencia [math]K^n cumple la recurrencia.

Las raíces de esa ecuación son [math]K_1=\frac{1+\sqrt{5}}{2} y [math]K_2=\frac{1-\sqrt{5}}{2}. Ahora si [math]G_n={\left(\frac{1+\sqrt{5}}{2}\right)}^n y [math]H_n={\left(\frac{1-\sqrt{5}}{2}\right)}^n
cualquier secuencia de la forma [math]F_n=aG_n+bH_n cumple la recurrencia. Entonces necesitamos encontrar [math]a y [math]b tales que:

• [math]0=F_0=aG_0+bH_0=a+b
• [math]1=F_1=aG_1+bH_1=\frac{a+b}{2}+\sqrt{5}\frac{a-b}{2}

Resolvemos el sistema y obtenemos [math]a=\frac{1}{\sqrt{5}}, [math]b=-\frac{1}{\sqrt{5}}.

Entonces la secuencia de Fibonacci tiene esta fórmula

[math]\displaystyle{F_n=a G_n + b H_n= \frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^n-\frac{1}{\sqrt{5}}{\left(\frac{1-\sqrt{5}}{2}\right)}^n=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}}

[Ivan]

En general la técnica para resolver recurrencias lineales es parecida a la que usamos para resolver Fibonacci: se buscan todas las soluciones de la forma [math]K^n con [math]K\neq 0 y se buscan constantes como hicimos en el caso de Fibonacci (hay que resolver un sistema, si tiene solución encontramos una fórmula para la recurrencia).

Veamos un caso de grado [math]3:

• [math]A_0=4
• [math]A_1=1
• [math]A_2=47
• [math]A_n=4A_{n-1}+11A_{n-2}-30A_{n-3}

Buscamos las soluciones de la forma [math]K^n. Nos queda que [math]K^3=4K^2+11K-30. Las raíces de este polinomio son [math]2, [math]-3 y [math]5. Luego buscamos una solucion de la forma [math]A_n=a 2^n + b (-3)^n + c 5^n. Ahora poniendo [math]n=0,1,2 obtenemos un sistema de [math]3 ecuaciones con [math]3 incógnitas que se va a poder despejar (esto tiene que ver con que las raíces sean todas distintas). Obtenemos [math]a=1, [math]b=2 y [math]c=1. Luego

[math]A_n=A_n= 2^n + 2 (-3)^n + 5^n

Pudimos resolver la recurrencia porque las raíces eran reales y todas distintas. Si hubiera habido dos raíces iguales nos habría quedado un sistema con mas ecuaciones que incógnitas que generalmente no tiene solución. Si hay raíces complejas puede no haber una formula linda para la recurrencia.

[Ivan]

Ahora veamos que pasa si el polinomio que se obtiene al reemplazar [math]A_i por [math]K^i tiene todas sus raíces reales pero hay raíces múltiples.

Si [math]\displaystyle A_n=\sum_{i=1}^{k} c_{k-i}A_{n-i}

Sea [math]\lambda una raíz del polinomio característico de la recurrencia o sea [math]\displaystyle P(x)=x^k-\sum_{i=1}^{k} c_{i}x^{i}

Queremos probar que si [math]\lambda tiene multiplicidad [math]m entonces [math]\lambda^n,\; n\lambda^n,\; \cdots \; n^{m-1}\lambda^n son soluciones de la recurrencia.

Para probar esto necesitamos el siguiente resultado:

Lema: Si [math]\lambda es raíz de [math]P(x) con multiplicidad [math]m entonces es raíz de [math]P^{(j)} (el polinomio que se obtiene como resultado de derivar [math]P [math]j veces) con multiplicidad [math]m-j.

Demostración:

Spoiler: mostrar

Supongamos que [math]P(x)=(x-\lambda)^m Q(x).
Entonces [math]{P'(x)=m (x-\lambda)^{m-1}Q(x)+(x-\lambda)^m Q'(x)=(x-\lambda)^{m-1}(mQ(x)+(x-\lambda)Q'(x))}. El lema sigue por inducción en [math]m.

Supongamos que [math]\lambda es raíz de [math]P con multiplicidad al menos [math]2. Tenemos [math]\displaystyle P(\lambda)=\lambda^k-\sum_{i=1}^{k} c_{k-i}\lambda^{k-i}=0.
Ademas por el lema [math]\displaystyle P'(\lambda)=k\lambda^{k-1}-\sum_{i=1}^{k} i c_{i}\lambda^{i-1}=0. Multiplicando por [math]\lambda
[math]\displaystyle k\lambda^{k}-\sum_{i=1}^{k} c_{i}(i\lambda^{i})=0, o sea que [math]n\lambda^n cumple la recurrencia.

La versión mas general se prueba por inducción: derivamos [math]P [math]j veces y usando la hipotesis inductiva vemos que [math]n^j\lambda^n cumple la recurrencia.

De este modo construimos [math]n soluciones de la recurrencia, podemos obtener [math]n ecuaciones con [math]n incognitas y si hay una solución conseguimos una fórmula cerrada para la recurrencia.

[Fredy10]

Del tema "Mas Recurrencias" obtenemos una linda idea para resolver recurrencias cuyas raices sean iguales, estas son del tipo [math]F_{n+1} = 2k F_n - k^2F_{n-1} otra que podemos llevar a esta dividiendo por el factror que multiplica a [math]F_{n+1}.
La unica raiz que satisface: [math]x^2-2kx+k^2 es exactamente [math]k, luego [math]F_n = k^n satisface la recurrencia anterior.
Basta encontrar otra secuencia más, y aqui nos resulta util el problema de Ivan, ya que este nos plantea hallar una recurrencia que es de la forma anterion, pero no es de la forma [math]jk^n con [math]j real, sino que tiene como una solucion de la recurrencia a [math]nk_n, la cual no es dificil ver, satisface [math]F_{n+1} = 2k F_n - k^2F_{n-1} por lo tanto las soluciones para este tipo de recurrencias, dados [math]F_0 y [math]F_1 son de la foma:
[math]\alpha k^n + \beta nk^n donde [math]\alpha y [math]\beta son:
[math]\alpha = F_0
[math]\beta = F_1 - kF_0
(esto no vale para [math]k=0, y aunque no tiene sentido este caso, es bueno aclararlo)
Notese con esto se resuelven las recurrencias de grado dos que poseen en la cuadratica