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 n-é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\geq k,$

onde $\varphi :\mathbb {N} \times X^{k}\to X$ é unha función que implica k elementos consecutivos da secuencia. Neste caso, son necesarios k 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,...

(secuencia A000045 na OEIS).

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 ten a mesma recorrencia con distintas condicións iniciais

$L_{n}=L_{n-1}+L_{n-2}$ coas condicións iniciais $L_{0}=2,L_{1}=1.$

A función xeradora da secuencia de Lucas é

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

A secuencia de números de Lucas é

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199,...

(secuencia A000032 na OEIS).

Coeficientes binomiais

Un exemplo sinxelo de relación de recorrencia multidimensional vén dado polos coeficientes binomiais ${\tbinom {n}{k}}$, que contan as formas de seleccionar $k$ elementos dun conxunto de $n$ elementos. Pódense calcular mediante a relación de recorrencia

${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},$

cos casos base ${\tbinom {n}{0}}={\tbinom {n}{n}}=1$. Usando esta fórmula para calcular os valores de todos os coeficientes binomiais xera unha matriz infinita chamada triángulo de Pascal. Os mesmos valores tamén se poden calcular directamente mediante unha fórmula diferente que non é unha recorrencia, senón que usa factoriais:

${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.$

E tamén se poden calcular cunha recorrencia unidimensional:

${\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k,$

co valor inicial ${\textstyle {\binom {n}{0}}=1}$.

Factorial

O factorial defínese pola relación de recorrencia

$n!=n(n-1)!\quad {\text{for}}\quad n>0,$

e a condición inicial

$0!=1.$

Este é un exemplo de recorrencia linear de orde 1 con coeficiente polinómico n.

Mapa loxístico

Outro exemplo de relación de recorrencia é o mapa loxístico:

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

cunha constante dada $r$. Dado o termo inicial $x_{0}$, vanse obtendo sucesivamente os termos posteriores.

Operador de diferenzas e ecuacións diferenciais

O operador de diferenzas denomínase comunmente $\Delta ,$ e defínese, en notación funcional, como

$(\Delta f)(x)=f(x+1)-f(x).$

É polo tanto é un caso especial de diferenza finita.

Cando se usa a notación de índices para secuencias, a definición pasa a ser

$(\Delta a)_{n}=a_{n+1}-a_{n}.$

Os parénteses ao redor de $\Delta f$ e $\Delta a$ omítense xeralmente, e $\Delta a_{n}$ debe entenderse como o termo do índice n na secuencia $\Delta a,$ e non $\Delta$ aplicado ao elemento $a_{n}.$

Dada a secuencia $a=(a_{n})_{n\in \mathbb {N} },$ as primeiras diferenzas de a son $\Delta a.$ As segundas diferenzas son $\Delta ^{2}a=(\Delta \circ \Delta )a=\Delta (\Delta a).$ Un simple cálculo demostra que

$\Delta ^{2}a_{n}=a_{n+2}-2a_{n+1}+a_{n}.$

As k-ésimas diferenzas defínense recursivamente como $\Delta ^{k}=\Delta \circ \Delta ^{k-1},$ e temos

$\Delta ^{k}a_{n}=\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}a_{n+k-t}.$

Esta relación pódese invertir, dando

$a_{n+k}=a_{n}+{k \choose 1}\Delta a_{n}+\cdots +{k \choose k}\Delta ^{k}(a_{n}).$

A ecuación de diferenzas de orde k é unha ecuación que implica as k primeiras diferenzas dunha secuencia ou función, do mesmo xeito que unha ecuación diferencial de orde k relaciona as k primeiras derivadas dunha función.

Nas dúas ecuacións vistas enriba cada unha é a inversa da outra, e as secuencias que son solución da ecuación diferencial son exactamente as que satisfán a relación de recorrencia.

Por exemplo, a ecuación da diferenzas

$3\Delta ^{2}a_{n}+2\Delta a_{n}+7a_{n}=0$

é equivalente á relación de recorrencia

$3a_{n+2}=4a_{n+1}-8a_{n},$

As ecuacións de diferenzas aseméllanse ás ecuacións diferenciais, e esta semellanza utilízase a miúdo para imitar os métodos de resolución de ecuacións diferenciables para aplicar á resolución das ecuacións de diferenzas e, polo tanto, as relacións de recorrencia.

Resolvendo

Resolución de relacións lineares de recorrencia con coeficientes constantes

Artigo principal: Recorrencia linear con coeficiente constantes.

Os métodos máis habituais de resolver este tipo de recorrencias é mediante funcións xeradoras ou mediante a forma matricial.

A forma matricial consiste en diagonalizar a matriz da recorrencia. Por exemplo, se consideremos a recorrencia de orde 3, $a_{n}=xa_{n-1}+ya_{n-2}+za_{n-3}$, con condicións iniciais $a_{0},a_{1},a_{2}$, temos

$${\begin{pmatrix}a_{n+1}\\a_{n}\\a_{n-1}\end{pmatrix}}={\begin{pmatrix}xa_{n}+ya_{n-1}+za_{n-2}\\a_{n}\\a_{n-1}\end{pmatrix}}={\begin{bmatrix}x&y&z\\1&0&0\\0&1&0\end{bmatrix}}{\begin{pmatrix}a_{n}\\a_{n-1}\\a_{n-2}\end{pmatrix}}$$

Que podemos expresar en forma abreviada como $v_{n+1}=Av_{n}$ e un vector de condicións iniciais $v_{0}={\begin{pmatrix}a_{2}\\a_{1}\\a_{0}\end{pmatrix}}$.

Se diagonalizamos $A=PDP^{-1}$, coa técnica de eigenvalores e eigenvectores, é fácil calcular a matriz $A$ elevada a unha potencia, neste caso por ter o termo inicial $a_{2}$ necesitamos elevar a $n-1$ para obter $a_{n+1}$, $A^{n-1}=PD^{n-1}P^{-1}$.

Así temos $${\begin{pmatrix}a_{n+1}\\a_{n}\\a_{n-1}\end{pmatrix}}=P{\begin{bmatrix}d_{0,0}^{n-1}&0&0\\0&d_{1,1}^{n-1}&0\\0&0&d_{2,2}^{n-1}\end{bmatrix}}P^{-1}v_{0}.$$.

Resolución de relacións de recorrencia non homoxéneas de primeira orde con coeficientes variables

Para a relación xeral de recorrencia linear non homoxénea de primeira orde con coeficientes variables:

$a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n}\neq 0,$

tamén hai un bo método para resolvela:

$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+hf_{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 xeralizada. 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_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{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^{*})|<1.$

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.

Véxase tamén

Bibliografía

• Batchelder, Paul M. (1967). An introduction to linear difference equations. Dover Publications. 
• Miller, Kenneth S. (1968). Linear difference equations. W. A. Benjamin. 
• Fillmore, Jay P.; Marx, Morris L. (1968). Linear recursive sequences. SIAM Rev. 10. pp. 324–353. JSTOR 2027658. 
• Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association. 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 4: Recurrences, pp. 62–90.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2 ed.). Addison-Wesley. ISBN 0-201-55802-5. 
• Enders, Walter (2010). Applied Econometric Times Series (3 ed.). Arquivado dende o orixinal o 2014-11-10. 
• Cull, Paul; Flahive, Mary; Robson, Robbie (2005). Difference Equations: From Rabbits to Chaos. Springer. ISBN 0-387-23234-6.  chapter 7.
• Jacques, Ian (2006). Mathematics for Economics and Business (Fifth ed.). Prentice Hall. pp. 551–568. ISBN 0-273-70195-9.  Chapter 9.1: Difference Equations.
• Minh, Tang; Van To, Tan (2006). Using generating functions to solve linear inhomogeneous recurrence equations (PDF). Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06. pp. 399–404. Arquivado dende o orixinal (PDF) o 2016-03-04. Consultado o 2014-08-07. 
• Polyanin, Andrei D. Difference and Functional Equations: Exact Solutions.  at EqWorld - The World of Mathematical Equations.
• Polyanin, Andrei D. Difference and Functional Equations: Methods.  at EqWorld - The World of Mathematical Equations.
• Wang, Xiang-Sheng; Wong, Roderick (2012). Asymptotics of orthogonal polynomials via recurrence relations. Anal. Appl. 10. pp. 215–235. arXiv:1101.4371. doi:10.1142/S0219530512500108. 

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

• "Recurrence relation". Encyclopedia of Mathematics. EMS Press. 2001 [1994]. 
• Weisstein, Eric W. "Recurrence Equation". MathWorld. 
• "OEIS Index Rec".  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).