Una relación de recurrencia es una ecuación, en la cual todo término de una sucesión se puede hallar en base a los anteriores.
Este tipo de funciones por sí solas, representan un problema a la hora de calcular términos muy grandes. Algunos de estos problemas son: (a) cometer algún error a la hora de calcular un término dado y por consiguiente, calcular mal los términos luego de éste. (b) no poder evaluar de forma eficiente términos muy grandes. (c) dificultad a la hora de conjeturar su comportamiento cuando \( n \to + \infty \).
Nuestra motivación principal, es hallar una expresión general para la relación de recurrencia, donde no sea necesario conocer los términos anteriores a uno dado.
Tipos de ecuaciones por recurrencia
1. Ecuaciones lineales: son aquellas en que las sucesiones por sí solas no están elevadas a un exponente particular (entiéndase que están elevadas a uno).
2. Ecuaciones homogéneas: son aquellas que uno de los miembros de la igualdad es cero.
3. Sistemas de ecuaciones: son conformados por al menos dos ecuaciones donde intervienen dos sucesiones en cada ecuación. La relación óptima sería que cada sucesión apareciera al menos una vez en cada ecuación.
Condiciones iniciales
Cada sucesión tiene infinitas fórmulas para calcular su término \( n \)-ésimo. Sin embargo, una vez aclarado el valor inicial de la sucesión, esta fórmula es única.
Un problema bien formulado, es aquel que además de presentar la ecuación de recurrencia, indica sus condiciones iniciales (la cantidad de condiciones iniciales dependen exclusivamente del tipo de relación).
A modo de ejemplo
Sea la sucesión definida por recurrencia:
Cita $$ \left\{\begin{matrix}
a_{n} = n·a_{n-1}\\
a_{0} = 1
\end{matrix}\right. $$
Notar que se trata de una recurrencia lineal, no homogénea, a términos variables. Más aún se tiene que \( a_{n} = n! \)
Cómo resolver algunas relaciones de recurrencia
De aquí en más se acuerda que resolver una relación de este tipo, es hallar un fórmula como la vista en el ejemplo anterior, y que cumple con nuestras motivaciones expuestas anteriormente.
1. Estudio del caso: relación de recurrencia lineal, homogénea, a coeficientes constantes, de primer orden
Este tipo de expresiones obedecen a la forma tipo:
Cita $$ \left\{\begin{matrix}
\lambda_{1}·a_{n} + \lambda_{2}·a_{n-1} = 0 \\
a_{0}
\end{matrix}\right. \mbox { donde } \lambda_{i} \in \mathbb {C}^{*} $$
A continuación se expone un posible razonamiento para hallar su solución. Notar que no es el único. Más adelante, para casos de mayor oden, se verá un algoritmo genérico para su cálculo.
Cita Deducción
El siguiente no vale más que para argumento deductorio. La veracidad de la afirmación debe ser probada (se recomienda inducción completa).
$$ \begin{align} a_{1} & = -\frac {\lambda_{2}}{\lambda_{1}}·a_{0} \\
a_{2} & = \left ( -\frac {\lambda_{2}}{\lambda_{1}} \right )·\left ( -\frac {\lambda_{2}}{\lambda_{1}}·a_{0} \right ) \\
a_{3} & = \left ( -\frac {\lambda_{2}}{\lambda_{1}} \right )·\left ( -\frac {\lambda_{2}}{\lambda_{1}} \right )·\left ( -\frac {\lambda_{2}}{\lambda_{1}}·a_{0} \right ) \\
& \vdots \\
a_{n} & = a_{0}·\left ( - \frac {\lambda_{2}}{\lambda_{1}} \right )^{n} \end{align} $$
La solución a estas expresiones, está dada por la forma:
Cita $$ a_{n} = a_{0}·\left ( - \frac {\lambda_{2}}{\lambda_{1}} \right )^{n} $$
2. Estudio del caso: relación de recurrencia lineal, homogénea, a coeficientes constantes, de segundo orden
Forma tipo:
Cita $$ \left\{\begin{matrix}
\lambda_{1}·a_{n} + \lambda_{2}·a_{n-1} + \lambda_{3}·a_{n-2} = 0 \\
a_{0}, a_{1}
\end{matrix}\right. \mbox { donde } \lambda_{i} \in \mathbb {C}; \lambda_{1}, \lambda_{3} \neq 0 $$
Cita Deducción
Se supone que tiene una raíz de la forma \( x^{n} \) (notar que fue el caso a que llegamos para orden uno). Reemplazando se tiene que:
$$ \lambda_{1}·x^{n} + \lambda_{2}·x^{n-1} + \lambda_{3}·x^{n-1} = 0 \overset{\div x^{n-2}}{\Rightarrow} \lambda_{1}·x^{2} + \lambda_{2}·x + \lambda_{3} = 0 $$
En base a esto, se tiene que la naturaleza de estas raíces está dada por el discriminante: \( \Delta = \lambda_{2}^{2} - 4·\lambda_{1}·\lambda_{3} \). Para cada caso expuesto en la siguiente tabla, se habrá de proceder de una manera distinta.
$$ \begin{array}{|c|c|}
\hline
\Delta > 0 & \mbox {Dos raíces reales distintas } r_{1} \mbox { y } r_{2} \\
\hline
\Delta = 0 & \mbox {Dos raíces reales iguales } r \\
\hline
\Delta < 0 & \mbox {Dos raíces complejas conjugadas } r_{1} \mbox { y } r_{2} \\
\hline
\end{array} $$
a. Caso en que \( \Delta > 0 \)
Cita $$ a_{n} = \alpha·r_{1}^{n} + \beta·r_{2}^{n} $$
b. Caso en que \( \Delta = 0 \)
Cita $$ a_{n} = \alpha·r^{n} + \beta·n·r^{n} $$
c. Caso en que \( \Delta < 0 \)
Este es el caso más curioso de los tres.
Cita $$ a_{n} = \alpha·r_{1}^{n} + \beta·r_{2}^{n} $$
Otra forma en que podríamos presentarlo es la siguiente:
Ejemplo: sucesión de Fibonacci
La sucesión de Fibonacci se define como \( a_{n} = a_{n-1} + a_{n - 2} \) bajo las condiciones iniciales \( a_{0} = 1, a_{1} = 1 \). Esta sucesión es conocida por describir el periodo de reproducción de los conejos. Partiendo de una pareja de conejos (un macho y una hembra), se podrá conocer la cantidad aproximada de parejas de conejos en un tiempo \( n \) medido en meses. Se pretende calcular cuántos conejos habrá en tres años.
Calculando las raíces de la homogénea:
$$ a_{n} - a_{n-1} - a_{n-2} = 0 \Rightarrow x^2 - x - 1 = 0 \Leftrightarrow x_{1,2} = \frac {1 \pm \sqrt {5}}{2} $$
Se obtiene la forma de la expresión:
$$ a_{n} = \alpha·\left ( \frac {1+\sqrt{5}}{2} \right )^n + \beta·\left ( \frac {1+\sqrt{5}}{2} \right )^n $$
Imponiendo las condiciones iniciales se tiene el siguiente sistema:
$$ \left\{\begin{matrix}
\alpha + \beta = 1 \\
\alpha·\left ( \frac {1+\sqrt{5}}{2} \right ) + \beta·\left ( \frac {1+\sqrt{5}}{2} \right ) = 1
\end{matrix}\right. \Leftrightarrow \alpha = \frac {5 + \sqrt{5}}{10} \wedge \beta = \frac {5 - \sqrt{5}}{10} $$
Obteniendo la fórmula para la sucesión de Fibonacci:
$$ a_{n} = \left ( \frac {5 + \sqrt{5}}{10} \right )·\left ( \frac {1+\sqrt{5}}{2} \right )^n + \left ( \frac {5 - \sqrt{5}}{10} \right )·\left ( \frac {1-\sqrt{5}}{2} \right )^n $$
Evaluando en el mes 36 (tercer año):
$$ \Rightarrow \boxed {a_{36} = 24.157.817} $$
3. Estudio del caso: relación de recurrencia lineal, homogénea, a coeficientes constantes, de orden \( n \).
Forma tipo:
Cita $$ \sum_{k=0}^{n} (\lambda_{k+1}·a_{n+k}) \mbox { donde } \lambda_{i} \in \mathbb {C}; \lambda_{1}, \lambda_{n} \neq 0 $$
Y se necesitan \( n \) condiciones iniciales.
Cita Deducción
Se procede análogamente a lo visto en el segundo orden. Se termina llegando a una expresión de la forma:
$$ \sum_{k=0}^{n} (\lambda_{k+1}·x^{n}) $$
Se utilizan los mismos criterios para raíces de polinomios característicos de segundo roden.
4. Estudio del caso: relación de recurrencia lineal, no-homogénea, a coeficientes constantes, de primer orden.
Forma tipo:
Cita $$ \lambda_{1}·a_{n} + \lambda_{2}·a_{n-1} = f(n) \mbox { donde } \lambda_{i} \in \mathbb {C}^{*} $$
Resolución
Este tipo de expresiones son más complicadas. Se utiliza el siguiente esquema para su resolución. Donde, en las partes anteriores ya se ha visto cómo calcular las raíces de la homogénea, aquí nos detendremos en cómo hallar una solución particular exclusiva de la parte no-homogénea.
Cita $$ S_{GENERAL} = S_{HOMOGÉNEA} + S_{PARTICULAR} $$
Comentario: para casos de orden superior se procede de forma análoga.
|