Relación de recorrencia

En matemáticas, unha **relación de recorrencia** é unha ecuación segundo a cal o enésimo termo dunha secuencia de números é igual a algunha combinación dos termos anteriores. Se temos k termos da ecuación para definir o termo n, ese número k chámase *orde* da relación. Se temos os valores dos primeiros k termos da secuencia, o resto da secuencia pódese calcular aplicando repetidamente a ecuación.

Nas *recorrencias lineares*, o termo -ésimo fórmase mediante unha función linear de k termos anteriores. Un exemplo famoso é a recorrencia dos números de Fibonacci,F_n=F_{n-1}+F_{n-2}onde a orde é 2 e a función linear é a suma dos dous termos anteriores. 

Este exemplo é unha recorrencia linear con coeficientes constantes, porque os coeficientes da función linear (1 e 1) son constantes que non dependen de n. Para estas recorrencias, pódese expresar o termo xeral da secuencia como unha expresión de forma explícita de n. 

Outro tipo de recorrencias son as recorrencias lineares con coeficientes polinómicos dependendo de n (ver ecuación p-recursiva e función holonómica).

Resolver unha relación de recorrencia significa obter unha solución en forma pechada: unha función non recursiva para o termo n-ésimo.

## Definición 
Unha *relación de recorrencia* é unha ecuación que expresa cada elemento dunha secuencia en función dos anteriores.

: u_n=\varphi(n, u_{n-1}, u_{n-2}, \ldots, u_{n-k})\quad\text{for}\quad n\ge k,

onde \varphi: \mathbb N\times X^k \to X é unha función que implica  elementos consecutivos da secuencia. Neste caso, son necesarios  valores iniciais para definir unha secuencia.

## Exemplos 
### Números de Fibonacci e de Lucas 
A recorrencia de orde 2 satisfeita polos números de Fibonacci é o exemplo típico dunha relación de recorrencia linear homoxénea con coeficientes constantes. A secuencia de Fibonacci defínese usando a recorrencia

: F_n = F_{n-1}+F_{n-2} coas condicións iniciais F_0 = 0, F_1 = 1.

Obtemos a secuencia de números de Fibonacci,
 

: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

.

A recorrencia pódese resolver mediante a fórmula de Binet, que implica potencias das dúas raíces do polinomio característico. t^2 = t + 1. A función xeradora da secuencia de Fibonacci é a función racional

: G.f.: \frac{t}{1-t-t^2}.

A secuencia de Lucas

: a_{n+1} - f_n a_n = g_n
: \frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{f_n a_n}{\prod_{k=0}^n f_k} = \frac{g_n}{\prod_{k=0}^n f_k}

: \frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{a_n}{\prod_{k=0}^{n-1} f_k} = \frac{g_n}{\prod_{k=0}^n f_k}

Sexa

: A_n = \frac{a_n}{\prod_{k=0}^{n-1} f_k},

Daquela

: A_{n+1} - A_n = \frac{g_n}{\prod_{k=0}^n f_k}
: \sum_{m=0}^{n-1}(A_{m+1} - A_m) = A_n - A_0 = \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}
: \frac{a_n}{\prod_{k=0}^{n-1} f_k} = A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}
: a_n = \left(\prod_{k=0}^{n-1} f_k \right) \left(A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}\right)

Se aplicamos a fórmula a a_{n+1} = (1 + h f_{nh}) a_n + hg_{nh} e tomamos o límite cando h \to 0, obtemos a fórmula para ecuacións diferenciais lineares de primeira orde con coeficientes variables; a suma convértese nunha integral e o produto convértese na función exponencial dunha integral.

### Resolución de relacións xerais de recorrencia lineares homoxéneas 
Moitas relacións homoxéneas de recorrencia linear poden resolverse mediante a función hiperxeométrica xeneralizada. Por exemplo, a solución a

: J_{n+1}=\frac{2n}{z}J_n-J_{n-1}

ven dada por

: J_n=J_n(z), 

a función de Bessel, mentres

: (b-n)M_{n-1} +(2n-b+z)M_n - nM_{n+1}=0 

resólvese con

: M_n=M(n,b;z) 

a función hiperxeométrica confluente. 

As secuencias que son solucións de ecuacións de diferenzas lineares con coeficientes polinómicos chámanse ecuacións p-recursivas. Para estas ecuacións de recorrencia específicas coñécense algoritmos que atopan solucións polinómicas, racionais (algoritmo de Abramov) ou hiperxeométricas (algoritmo de Petkovšek).

### Resolver ecuacións en diferenzas racionais de primeira orde 
Unha ecuación de diferenzas racional de primeira orde ten a forma w_{t+1} = \tfrac{aw_t+b}{cw_t+d} . Tal ecuación pódese resolver escribindo w_t como transformación non linear doutra variable x_t que evolúe linearmente. Así logo pódense usar métodos estándar para resolver a ecuación de diferenzas lineares en x_t.

## Estabilidade 
### Estabilidade das recorrencias lineares 
A recorrencia linear de orde d,

: a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d}, 

ten unha ecuación característica de tipo

: \lambda^d - c_1 \lambda^{d-1} - c_2 \lambda^{d-2} - \cdots - c_d \lambda^0 =0. 

A recorrencia é estable, co significado de que as iteracións converxen asintóticamente a un valor fixo, se e só se os autovalores (é dicir, as raíces da ecuación característica), sexan reais ou complexas, son todos menores que a unidade en valor absoluto.

### Estabilidade das recorrencias non lineares de primeira orde 
Considere a recorrencia non linear de primeira orde

: x_n=f(x_{n-1}).

Esta recorrencia é localmente estable, o que significa que converxe a un punto fixo x^* desde puntos suficientemente próximos x^*, se a pendente de f no proximidade de x^* é menor que a unidade en valor absoluto: é dicir,

: | f' (x^*) | 

Unha recorrencia non linear podería ter varios puntos fixos, nese caso algúns puntos fixos poden ser localmente estables e outros localmente inestables; para unha *f* continua dous puntos fixos adxacentes non poden ser ambos os dous localmente estables.

## Relación coas ecuacións diferenciais 
Ao resolver unha ecuación diferencial ordinaria de forma numérica, normalmente atopámonos cunha relación de recorrencia. Por exemplo, ao resolver o problema do valor inicial

: y'(t) = f(t,y(t)), \ \ y(t_0)=y_0,

co método de Euler e un tamaño de paso h, calculamos os valores

: y_0=y(t_0), \ \ y_1=y(t_0+h), \ \ y_2=y(t_0+2h), \ \dots

coa recorrencia

: \, y_{n+1} = y_n + hf(t_n,y_n), t_n = t_0 + nh 

Os sistemas de ecuacións diferenciais lineares de primeira orde poden discretizarse analíticamente usando os métodos mostrados no artigo de  discretización.

## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 
* 
* 
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 1990. . Chapter 4: Recurrences, pp.&nbsp;62–90.
*
*
* chapter 7.
*  Chapter 9.1: Difference Equations.
* 
*  at EqWorld - The World of Mathematical Equations.
*  at EqWorld - The World of Mathematical Equations.
*
### Outros artigos 
* Función holonómica
* Función iterada
* Polinomios ortogonais
* Recursión
* Fracción continua
* Coeficiente binomial
* Integración por fórmulas de redución
* Indución matemática
* Ecuación diferencial

### Ligazóns externas 
* 
* 
*  OEIS miles de recorrencias lineares, ordenadas por orde e sinatura.
* Fibonacci Quarterly publicación con máis de 60 anos de artigos sobre recorrencias (en aberto excluíndo os últimos 5 anos).