Relación de recurrencia

En matemática, una relación de recurrencia es una ecuación que define una secuencia recursiva; cada término de la secuencia es definido como una función de términos anteriores.^[1]​

Definición

Una ecuación recurrente es un tipo específico de relación de recurrencia. Una relación de recurrencia para la sucesión ${\displaystyle a_{0},a_{1},a_{2},\ldots }$ es una ecuación que relaciona ${\displaystyle a_{n}\,}$ con alguno de sus predecesores ${\displaystyle a_{0},a_{1},\ldots ,a_{n-1}}$. Las condiciones iniciales para la sucesión ${\displaystyle a_{0},a_{1},\ldots }$ son valores dados en forma explícita para un número finito de términos de la sucesión.^[2]​

Resolver una relación de recurrencia consiste en determinar una fórmula explícita (cerrada) para el término general ${\displaystyle a_{n}\,}$, es decir una función no recursiva de n.

Hay tres métodos para resolver relaciones recurrentes: iteración, transformada Z y un método especial que se aplica a las relaciones de recurrencia lineales homogéneas con coeficientes constantes.

Un ejemplo de una relación de recurrencia es el siguiente:

${\displaystyle x_{n+1}=rx_{n}(1-x_{n})\,}$

Algunas definiciones de recurrencia pueden tener relaciones muy complejas (caóticas), y sus comportamientos a veces son estudiados por los físicos y matemáticos en un campo conocido como análisis no lineal.

Resolución

Por hipótesis comprobada

La forma más sencilla para resolver una relación de recurrencia es formular una posible solución (hipótesis) y comprobar por inducción la validez de la misma.

En el caso de las "Torres de Hanoi", siendo ${\displaystyle t}$ el número de pasos para resolver el problema con ${\displaystyle n}$ discos, ${\displaystyle t_{n}}$ está dado por la siguiente ecuación de recurrencia:

${\displaystyle t_{1}:=1;\,t_{n}:=2t_{n-1}+1}$

Resolver la recurrencia sería encontrar la ecuación que nos da el valor de ${\displaystyle t_{n}}$ en términos de ${\displaystyle n}$.

Al analizar la correspondencia para cada valor de ${\displaystyle t_{n}}$ con n desde ${\displaystyle \{1,2,3,4,5\}\rightarrow \{1,3,7,15,31\}}$ especulamos que quizás la solución sea ${\displaystyle t_{n}:=2^{n}-1}$, por lo que para comprobarla se procede a sustituir la hipótesis en la ecuación de recurrencia:

${\displaystyle t_{n}=2t_{n-1}+1=2(2^{n-1}-1)+1=2({\frac {2^{n}}{2}}-1)+1=(2^{n}-2)+1=2^{n}-1}$

comprobándose la hipótesis como verdadera.^[3]​

Iteración

Para resolver una relación de recurrencia asociada a la sucesión: ${\displaystyle a_{0},a_{1},a_{2}\,}$ por iteración, utilizamos la relación de recurrencia para escribir el n-ésimo término ${\displaystyle a_{n}\,}$ en términos de algunos de sus predecesores. Luego utilizamos de manera sucesiva la relación de recurrencia para reemplazar cada uno de los términos por algunos de sus predecesores. Continuamos hasta llegar a alguno de los casos base.

Recurrencias Lineales

Una relación de recurrencia es lineal de orden k si tiene la siguiente estructura:

${\displaystyle c_{0}(n)a_{n}+c_{1}(n)a_{n-1}+...+c_{k-1}(n)a_{n-k+1}+c_{k}(n)a_{n-k}\,=F(n)}$

para ${\displaystyle n\geq k}$, siendo ${\displaystyle c_{i}(n)\,}$ funciones reales de ${\displaystyle n\,}$, y ${\displaystyle F(n)\,}$ una función de n.

El adjetivo lineal indica que cada término de la secuencia está definido como una función lineal de sus términos anteriores. El orden de una relación de recurrencia lineal es el número de términos anteriores exigidos por la definición.

En la relación ${\displaystyle a_{n}=a_{n-2}\,}$ el orden es dos, porque debe haber al menos dos términos anteriores (ya sean usados o no).

Ejemplos :

${\displaystyle 3a_{n}-{n-1}a_{n-1}+2a_{n-2}=0\,}$

Ecuación de Recurrencia lineal homogénea con coeficientes constantes

Se llama ecuación de recurrencia lineal homogénea de orden k, con coeficientes constantes, a una expresión del tipo:

${\displaystyle a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{n-k}=0,c_{i}\in \mathbf {R} ,c_{k}\neq 0}$

Para poder encontrar una solución, hacen falta unas condiciones de contorno o iniciales ${\displaystyle a_{0},a_{1},\cdots ,a_{k-1}}$, siendo k el grado de la ecuación.

La recurrencia lineal, junto con las condiciones iniciales ${\displaystyle a_{0},\cdots ,a_{k-1}}$, determinan la secuencia única.

Sea la ecuación de recurrencia lineal homogénea de orden k anterior, se denomina ecuación característica a la ecuación de grado k:

${\displaystyle x^{k}=c_{1}x^{k-1}+\cdots +c_{k}}$

La generación de la función racional

Las secuencias lineales recursiva son precisamente las secuencias cuya función de generación es una función racional: el denominador es el polinomio auxiliar (a una transformación), y el numerador se obtiene con los valores iniciales.

El caso más sencillo son las secuencias periódicas,${\displaystyle a_{n}=a_{n-d}}$, n≥d que tienen secuencia ${\displaystyle a_{0},a_{1},\cdots ,a_{d-1},a_{0},\cdots }$ y función de generación una suma de una serie geométrica:

${\displaystyle {\begin{array}{ll}{\cfrac {a_{0}+a_{1}x^{1}+\dots +a_{d-1}x^{d-1}}{1-x^{d}}}=&(a_{0}+a_{1}x^{1}+\dots +a_{d-1}x^{d-1})+\\&(a_{0}+a_{1}x^{1}+\dots +a_{d-1}x^{d-1})x^{d}+\\&(a_{0}+a_{1}x^{1}+\dots +a_{d-1}x^{d-1})x^{2d}+\\&\dots \end{array}}}$

Más general, dada la relación de recurrencia:

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{d}a_{n-d}\,}$

con función de generación

${\displaystyle a_{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots }$

la serie es aniquilada por ${\displaystyle a_{k}}$ y anteriormente por el polinomio:

${\displaystyle 1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}}$

Eso es, multiplicando la función de generación por el polinomio

${\displaystyle b_{n}=a_{n}-c_{1}a_{n-1}-c_{2}a_{n-2}-\cdots -c_{d}a_{n-d}}$

como el coeficiente en ${\displaystyle x^{n}}$, que desaparece (por la relación de recurrencia) para n ≥ d. Así:

${\displaystyle (a_{0}+a_{1}x^{1}+a_{2}x^{2}+\dots )(1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d})=(b_{0}+b_{1}x^{1}+b_{2}x^{2}+\dots +b_{d-1}x^{d-1})}$

como dividiendo:

${\displaystyle a_{0}+a_{1}x^{1}+a_{2}x^{2}+\dots ={\cfrac {b_{0}+b_{1}x^{1}+b_{2}x^{2}+\dots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d}}}}$

expresando la función de generación como una función racional. El denominador es ${\displaystyle x^{d}p(1/x)}$, una transformación del polinomio auxiliar (equivalente, invirtiendo el orden de los coeficientes); también se puede usar cualquier múltiplo de esta, pero esta normalización es elegida por ambas porque la relación simple del polinomio auxiliar, y de ese modo ${\displaystyle b_{0}=a_{0}}$.

Relación con la diferencia de ecuaciones

Dada una secuencia ${\displaystyle \{a_{n}\}\,}$ de números reales: la primera diferencia ${\displaystyle d(a_{n})\,}$ se define como ${\displaystyle a_{n}-a_{n-1}\,}$

La segunda diferencia ${\displaystyle d^{2}(a_{n})\,}$ se define como ${\displaystyle d(a_{n})-d(a_{n-1})\,}$,

que se puede simplificar a ${\displaystyle a_{n}-2a_{n-1}+a_{n-2}\,}$.

Más general: la diferencia ${\displaystyle d^{k}\,}$ se define como ${\displaystyle d^{k-1}(a_{n})-d^{k-1}(a_{n-1})\,}$

A diferencia de la ecuación es una ecuación compuesta por ${\displaystyle a_{n}}$ y sus diferencias. Cada relación de recurrencia puede ser formulada como una ecuación de diferencia. Por el contrario, cada ecuación de diferencia puede ser formulada como una relación de recurrencia. Algunos autores así utilizan los dos términos intercambiables. Por ejemplo, la ecuación de la diferencia:

${\displaystyle 3d^{2}(a_{n})+2d(a_{n})+7a_{n}=0\,}$

es equivalente a la relación de recurrencia:

${\displaystyle 12a_{n}=8a_{n-1}-3a_{n-2}\,}$

De este modo se puede resolver relaciones de recurrencia por la reiteración como ecuaciones diferencia, y luego la solución de la ecuación de diferencia, análogamente como una solución de ecuaciones diferenciales ordinarias.

Ver escala de tiempo de cálculo para la unificación de la teoría de las ecuaciones de diferencia con la de las ecuaciones diferenciales.

Resolución

Sean

${\displaystyle c_{0}a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{n-k}=0}$

una ecuación de recurrencia lineal homogénea, ${\displaystyle x^{k}+c_{n-1}x^{k-1}+\cdots +c_{n-k}}$ su ecuación característica y, ${\displaystyle x_{1},x_{2},\cdots ,x_{s}}$ las raíces de la ecuación característica con multiplicidades ${\displaystyle m_{1},m_{2},\cdots ,m_{s}}$ respectivamente. La solución de esta ecuación sería:

${\displaystyle a_{n}=P_{1}(n)(x_{1})^{n}+P_{2}(n)(x_{2})^{n}+\cdots +P_{s}(n)(x_{s})^{n}}$

Con ${\displaystyle P_{i}(n)\ }$ el polinomio de grado menor o igual que ${\displaystyle m_{i}-1\,}$. Para poder calcular los coeficientes de los polinomios ${\displaystyle P_{i}(n)\,}$, necesitamos saber las condiciones iniciales de la ecuación de recurrencia.

Ejemplo : Números de Fibonacci

Los números de Fibonacci están definidos usando la siguiente relación de recurrencia lineal:

${\displaystyle F_{n}=F_{n-1}+F_{n-2}\,}$

con los valores iniciales:

${\displaystyle F_{1}=1\,}$

${\displaystyle F_{2}=1\,}$

La secuencia de los números de Fibonacci comienza: 1, 1, 2, 3 ,5, 8, 13, 21 ,34, 55, 89... El objetivo de la resolución de la ecuación de recurrencia es encontrar una forma cerrada para calcular los números de Fibonacci.

La ecuación característica es la siguiente:

${\displaystyle x^{2}-x-1=0\,}$

${\displaystyle x_{1}={\frac {1+{\sqrt {5}}}{2}}\,}$

${\displaystyle x_{2}={\frac {1-{\sqrt {5}}}{2}}\,}$

por lo tanto, la solución general es:

${\displaystyle F(n)=A_{1}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+A_{2}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}$

Para hallar el valor de ${\displaystyle A_{1}}$ y ${\displaystyle A_{2}}$ resolvemos las siguientes ecuaciones:

${\displaystyle F_{1}=A_{1}\left({\frac {1+{\sqrt {5}}}{2}}\right)+A_{2}\left({\frac {1-{\sqrt {5}}}{2}}\right)}$

${\displaystyle F_{2}=A_{1}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{2}+A_{2}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{2}}$

Entonces:

${\displaystyle A_{1}={\frac {1}{\sqrt {5}}}}$

y

${\displaystyle A_{2}={\frac {-1}{\sqrt {5}}}}$

La forma cerrada para los números de Fibonacci es:

${\displaystyle F(n)={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)}$

Ecuación de Recurrencia lineal no homogénea con coeficientes constantes

Recibe el nombre de ecuación de recurrencia lineal no homogénea de grado k, con coeficientes constantes, una expresión del tipo: ${\displaystyle c_{0}a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{n-k}=F(n),c_{i}\in \mathbf {R} ,c_{k}\neq 0}$.

Resolución

La solución general sería: ${\displaystyle a_{n}=a_{n}^{(h)}+a_{n}^{(p)}}$ , donde ${\displaystyle a_{n}^{(h)}}$ es la solución de la ecuación de recurrencia lineal homogénea asociada es decir la ecuación : ${\displaystyle c_{0}a_{n}+c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{k}a_{n-k}=0,c_{i}\in \mathbf {R} ,c_{k}\neq 0}$ y donde ${\displaystyle a_{n}^{(p)}}$ es la solución particular que depende de la función F(n). Por lo tanto los pasos a seguir serían, primero calcular la solución de la ecuación homogénea, calcular una solución particular para F(n) y sumarla a la homogénea, y a continuación aplicar las condiciones iniciales para calcular las constantes. En la siguiente tabla, encontramos cuales son las posibles soluciones particulares:

${\displaystyle F(n)}$		${\displaystyle {a_{n}}^{(p)}}$
${\displaystyle C,{\rm {constante}}}$		${\displaystyle C_{0},{\rm {constante}}}$
${\displaystyle n}$		${\displaystyle C_{0}+C_{1}n}$
${\displaystyle n^{2}}$		${\displaystyle C_{0}+C_{1}n+C_{2}n^{2}}$
${\displaystyle n^{t},t\in \mathbf {Z} ^{+}}$		${\displaystyle C_{0}+C_{1}n+\cdots +C_{t}n^{t}}$
${\displaystyle r^{n},r\in \mathbf {R} }$		${\displaystyle C_{0}r^{n}}$
${\displaystyle n^{t}r^{n}}$		${\displaystyle r^{n}(C_{0}+C_{1}n+\cdots +C_{t}n^{t})}$
${\displaystyle \sin(An),A\in \mathbf {R} }$		${\displaystyle C_{0}\sin(An)+C_{1}\cos(An)}$
${\displaystyle \cos(An),A\in \mathbf {R} }$		${\displaystyle C_{0}\sin(An)+C_{1}\cos(An)}$
${\displaystyle r^{n}\sin(An),A\in \mathbf {R} }$		${\displaystyle C_{0}r^{n}\sin(An)+C_{1}r^{n}\cos(An)}$
${\displaystyle r^{n}\cos(An),A\in \mathbf {R} }$		${\displaystyle C_{0}r^{n}\sin(An)+C_{1}r^{n}\cos(An)}$

• Consideraciones:

1.- Si F(n) es una combinación lineal de algunas de las funciones de la tabla anterior, su solución particular es la combinación lineal de las soluciones particulares de esas mismas funciones.

2.- Si uno de los sumandos de F(n) es el producto de una constante por una solución de la ecuación característica homogénea asociada, entonces es necesario multiplicar la solución particular correspondiente a este sumando por la menor potencia de n, tal que este nuevo producto no sea solución de la ecuación característica homogénea asociada.

Ejemplo: Torres de Hanói

La ecuación de recurrencia asociada con el problema de las Torres de Hanói es la siguiente:

${\displaystyle T_{n}=2T_{n-1}+1\,}$

Con las condiciones iniciales:

${\displaystyle T_{1}=1\,}$

Se resuelve la siguiente homogénea:

${\displaystyle T_{n}^{(h)}=2T_{n-1}}$

La ecuación característica es: ${\displaystyle x-2=0}$, entonces ${\displaystyle x=2}$

Entonces : ${\displaystyle T_{n}^{(h)}=A2^{n}}$

A continuación, se resuelve la ecuación particular:${\displaystyle T_{n}^{(p)}=B=2B+1}$, entonces ${\displaystyle B=-1}$.

${\displaystyle T_{n}=A2^{n}-1\,}$, entonces igualando con las condiciones iniciales la solución es : ${\displaystyle T_{n}=2^{n}-1\,}$

Recurrencias No lineales

Para resolver recurrencias no lineales tenemos muchas opciones de las cuales:

• Buscar transformaciones o cambios de variables que hagan la recurrencia lineal.
• Para el caso ${\displaystyle t(n)=a\cdot t\left({\frac {n}{b}}\right)+f(n)}$ , hay un teorema muy útil que es el Teorema Maestro.

La recurrencia en la computación

La conexión con el análisis de algoritmos estriba en que la forma que se ha adoptado para medir las complejidades, utiliza funciones cuyo dominio son los números naturales, o en otras palabras, sucesiones. Si el algoritmo es recurrente, es de esperarse que las complejidades, como funciones que estiman la demanda de recursos a lo largo de la ejecución, sean sucesiones que satisfacen ciertas ecuaciones de recurrencia. En un algoritmo recursivo, la función t(n) que establece su complejidad viene dada por una ecuación de recurrencia. Una ecuación de recurrencia nos permiten indicar el tiempo de ejecución para los distintos casos del algoritmo recursivo (casos base y recursivo).

Ejemplo : Cálculo del factorial

int Fact(int n){
        if(n>=0 && n<=1)  //Si n es 0 o es el número 1, el factorial es 1 
            return 1;
        else
        return n*Fact(n-1);
}

Considerando el producto como operación básica, podemos construir la ecuación recurrente para calcular la complejidad del algoritmo como sigue:

Como se ve en el código el caso base es para n<=1, para estos valores de n el número de multiplicaciones que se realiza es 0. Y en otro caso es 1 más las necesarias para calcular el factorial de n-1. Así construimos la función recurrente:

${\displaystyle t(n)={\begin{cases}1&{\mbox{si }}n\leq 1\\t(n-1)+1&{\mbox{si }}n>1\end{cases}}}$

Ahora si resolvemos la ecuación recurrente sabremos la complejidad de este algoritmo en función de n. Procedemos a resolver esta ecuación recurrente no lineal:

${\displaystyle t(n)=t(n-1)-1\,}$

resolvemos la homogénea:

${\displaystyle t(n)=t(n-1)\longrightarrow \quad r-1=0\longrightarrow \quad r=1a_{n}^{h}=c1^{n}\longrightarrow \quad a_{n}^{h}=c}$

resolvamos ahora la particular:

como la particular' coincide con la r, debemos aumentar el grado multiplicando por n

${\displaystyle \longrightarrow a_{n}^{p}=n1^{n}\longrightarrow \quad a_{n}^{p}=n}$

por lo que la solución de la ecuación recurrente queda como sigue:

${\displaystyle t(n)=c+n\,}$

Ahora calculamos c utilizando el caso base, t(1) = 1

${\displaystyle t(1)=c+1=1\longrightarrow \quad c=0}$

ya tenemos la solución: t(n) = n

La ecuación que nos ha quedado es de grado 1 por lo que la complejidad es del orden exacto de n -> θ(n)

Por ejemplo para calcular el factorial de 3 necesitaremos t(3) productos lo que es igual a

${\displaystyle 3-1=2\longrightarrow \quad 3\cdot (2\cdot (1))}$

Como vemos son 2 productos como nos ha devuelto la ecuación.

Aplicaciones

Biología

Algunas de las ecuaciones de diferencia más conocidas tienen sus orígenes en el intento de modelar la dinámica de la población. Por ejemplo, los números de Fibonacci se utilizaron una vez como modelo para el crecimiento de una población de conejos.

El mapa logístico se utiliza directamente para modelar el crecimiento de la población, o como punto de partida para modelos más detallados de dinámica poblacional. En este contexto, a menudo se utilizan ecuaciones de diferencias acopladas para modelar la interacción de dos o más poblaciones. Por ejemplo, el modelo de Nicholson-Bailey. Las ecuaciones de Integrodiferencia son una forma de relación de recurrencia importante para la ecología espacial. Estas y otras ecuaciones de diferencias son particularmente adecuadas para modelar poblaciones univoltinas.

Informática

Las relaciones de recurrencia son también de fundamental importancia en el análisis de algoritmos. Si un algoritmo está diseñado para que rompa un problema en subproblemas más pequeños divide y vencerás, su tiempo de ejecución se describe por una relación de recurrencia.

Un ejemplo simple es el tiempo que un algoritmo toma para encontrar un elemento en un vector ordenado con elementos {N}, en el peor de los casos.

Un algoritmo ingenuo buscará de izquierda a derecha, un elemento a la vez. El peor escenario posible es cuando el elemento requerido es el último, por lo que el número de comparaciones es {N} .

Un algoritmo mejor se llama búsqueda binaria. Sin embargo, requiere un vector clasificado. Comprueba primero si el elemento está en el centro del vector. Si no, entonces comprobará si el elemento medio es mayor o menor que el elemento buscado. En este punto, la mitad del vector puede ser descartada, y el algoritmo puede ser ejecutado de nuevo en la otra mitad. El número de comparaciones será dado por: C1 = 1; Cn = 1 + C(n/2), aproximado al log(2) de n.

Economía

Las relaciones de recurrencia, especialmente las relaciones de recurrencia lineal, se utilizan ampliamente tanto en la economía teórica como en la empírica. En particular, en macroeconomía se podría desarrollar un modelo de varios sectores amplios de la economía (el sector financiero, el sector de bienes, el mercado de trabajo, etc.), en el que las acciones de algunos agentes dependen de variables rezagadas. El modelo se resolvería para los valores actuales de variables clave (tasa de interés, PIB real, etc.) en términos de variables exógenas y variables endógenas retardadas. Véase también análisis de series temporales.

Entre otras:

• En la óptica
• En la teoría de la probabilidad
• En el estudio de los árboles binarios, pilas y algoritmos de ordenación

Véase también

• Teorema Maestro
• Recursividad

Referencias

1. Lehman, Leighton y Meyer (2010). Mathematics for Computer Science. p. 283. 
2. Johnsonbaugh, Richard (2005). Matemáticas Discretas. Pearson Education. p. 280. ISBN 970-26-0637-3. 
3. Lehman, Leighton y Meyer (2010). Mathematics for Computer Science. p. 287. 

• Datos: Q740970