Ver o código fonte de «Relación de recorrencia»

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

Nas ''recorrencias lineares'', o termo {{Mvar|n}}-ésimo fórmase mediante unha [[función linear]] de <math>k</math> termos anteriores. Un exemplo famoso é a recorrencia dos [[Sucesión de Fibonacci|números de Fibonacci]],<math display="block">F_n=F_{n-1}+F_{n-2}</math>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 <math>n</math>. Para estas recorrencias, pódese expresar o termo xeral da secuencia como unha expresión de forma explícita de <math>n</math>. 

Outro tipo de recorrencias son as recorrencias lineares con coeficientes polinómicos dependendo de <math>n</math> (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 <math>n</math>-ésimo.

== Definición ==
Unha ''relación de recorrencia'' é unha ecuación que expresa cada elemento dunha [[Sucesión (matemáticas)|secuencia]] en función dos anteriores.

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

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


== Exemplos ==

=== Números de Fibonacci e de Lucas ===
A recorrencia de orde 2 satisfeita polos [[Sucesión de Fibonacci|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

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

Obtemos a secuencia de números de Fibonacci,
<ref name="koshy">{{Cita libro|
  title=Fibonacci and Lucas Numbers With Applications|
  author=Thomas Koshy|
  year=2018|  url=https://api.semanticscholar.org/CorpusID:123044645
}}</ref> 


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

{{OEIS|id=A000045}}.

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

: <math>G.f.: \frac{t}{1-t-t^2}.</math>

A secuencia de Lucas<ref name="koshy"/> ten a mesma recorrencia con distintas condicións iniciais

: <math>L_n = L_{n-1}+L_{n-2}</math> coas condicións iniciais <math>L_0 = 2, L_1 = 1.</math>

A función xeradora da secuencia de Lucas é

: <math>G.f.: \frac{2-t}{1-t-t^2}.</math>

A secuencia de números de Lucas é 

: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199,...
{{OEIS|id=A000032}}.

=== Coeficientes binomiais ===
Un exemplo sinxelo de relación de recorrencia multidimensional vén dado polos [[Coeficiente binomial|coeficientes binomiais]] <math>\tbinom{n}{k}</math>, que contan as formas de seleccionar <math>k</math> elementos dun conxunto de <math>n</math> elementos. Pódense calcular mediante a relación de recorrencia

: <math>\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k},</math>

cos casos base <math>\tbinom{n}{0}=\tbinom{n}{n}=1</math>. 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 [[Factorial|factoriais]]:

: <math>\binom{n}{k}=\frac{n!}{k!(n-k)!}.</math>

E tamén se poden calcular cunha recorrencia unidimensional:

:<math>\binom n k = \binom n{k-1}(n-k+1)/k,</math>


co valor inicial <math display="inline">\binom n 0 =1</math>. 

=== Factorial ===
O [[factorial]] defínese pola relación de recorrencia

: <math>n!=n(n-1)!\quad\text{for}\quad n>0,</math>

e a condición inicial

: <math>0!=1.</math>

Este é un exemplo de ''recorrencia linear de orde 1 con coeficiente polinómico'' {{Mvar|n}}.

=== Mapa loxístico ===
Outro exemplo de relación de recorrencia é o [[mapa loxístico]]:

: <math>x_{n+1} = r x_n (1 - x_n),</math>

cunha constante dada <math>r</math>. Dado o termo inicial <math>x_0</math>, vanse obtendo sucesivamente os termos posteriores.

== Operador de diferenzas e ecuacións diferenciais ==
O '''operador de diferenzas''' denomínase comunmente <math>\Delta,</math> e defínese, en [[Función|notación funcional]], como
: <math>(\Delta f)(x)=f(x+1)-f(x).</math>

É polo tanto é un caso especial de [[diferenza finita]].

Cando se usa a notación de índices para secuencias, a definición pasa a ser
: <math>(\Delta a)_n= a_{n+1} - a_n.</math>

Os parénteses ao redor de <math>\Delta f</math> e <math>\Delta a</math> omítense xeralmente, e <math>\Delta a_n</math> debe entenderse como o termo do índice {{Mvar|n}} na secuencia <math>\Delta a,</math> e non <math>\Delta</math> aplicado ao elemento <math>a_n.</math>

Dada a [[Sucesión (matemáticas)|secuencia]]  <math>a=(a_n)_{n\in \N},</math> as primeiras diferenzas de {{Mvar|a}} son <math>\Delta a.</math> As segundas diferenzas son <math>\Delta^2 a=(\Delta\circ\Delta)a= \Delta(\Delta a).</math> Un simple cálculo demostra que

: <math>\Delta^2 a_n= a_{n+2} - 2a_{n+1} + a_n.</math>

As {{Mvar|k}}''-ésimas diferenzas'' defínense recursivamente como <math>\Delta^k=\Delta\circ \Delta^{k-1},</math> e temos

: <math>\Delta^k a_n = \sum_{t=0}^k (-1)^t \binom{k}{t} a_{n+k-t}.</math>

Esta relación pódese invertir, dando
: <math>a_{n+k} = a_n + {k\choose 1} \Delta a_n + \cdots + {k\choose k} \Delta^k(a_n).</math>
A '''ecuación de diferenzas''' de orde {{Mvar|k}} é unha ecuación que implica as {{Mvar|k}} primeiras diferenzas dunha secuencia ou función, do mesmo xeito que unha [[Ecuación diferencial ordinaria|ecuación diferencial]] de orde {{Mvar|k}} relaciona as {{Mvar|k}} primeiras [[Derivada|derivadas]] dunha función.

Nas dúas ecuacións vistas enriba cada unha é a [[Función inversa|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
: <math>3\Delta^2 a_n + 2\Delta a_n + 7a_n = 0</math>
é equivalente á relación de recorrencia
: <math>3a_{n+2} = 4a_{n+1} - 8a_n,</math>
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 ===
{{main|Recorrencia linear con coeficiente constantes}}

Os métodos máis habituais de resolver este tipo de recorrencias é mediante [[función xeradora|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, <math>a_n = xa_{n-1} + ya_{n-2} +za_{n-3}</math>, con condicións iniciais <math>a_0, a_1, a_2</math>, temos

<math display="block"> \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} </math>

Que podemos expresar en forma abreviada como <math>v_{n+1}=A v_n</math> e un  vector de condicións iniciais  <math>v_0=\begin{pmatrix}a_2 \\ a_1 \\ a_{0} \end{pmatrix}</math>.

Se diagonalizamos <math>A=PDP^{-1}</math>, coa técnica de [[Valor propio, vector propio e espazo propio|eigenvalores e eigenvectores]], é fácil calcular a matriz <math>A</math> elevada a unha potencia, neste caso por ter o termo inicial <math>a_2</math> necesitamos elevar a <math>n-1</math> para obter <math>a_{n+1}</math>,  <math>A^{n-1}=PD^{n-1}P^{-1}</math>.

Así temos 
<math display="block"> \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. </math>.

=== 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:

: <math>a_{n+1} = f_n a_n + g_n, \qquad f_n \neq 0,</math>

tamén hai un bo método para resolvela: <ref>{{cita web |url=http://faculty.pccu.edu.tw/%7Emeng/Math15.pdf |title=Chapter 15 Difference Equations and the Z-Transforms|access-date=2010-10-19 |archive-url=https://web.archive.org/web/20100705023731/http://faculty.pccu.edu.tw/~meng/Math15.pdf |archive-date=2010-07-05 }}</ref>

: <math>a_{n+1} - f_n a_n = g_n</math>
: <math>\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}</math>

: <math>\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}</math>

Sexa

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

Daquela

: <math>A_{n+1} - A_n = \frac{g_n}{\prod_{k=0}^n f_k}</math>
: <math>\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}</math>
: <math>\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}</math>
: <math>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)</math>

Se aplicamos a fórmula a <math>a_{n+1} = (1 + h f_{nh}) a_n + hg_{nh}</math> e tomamos o límite cando <math>h \to 0</math>, 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

: <math>J_{n+1}=\frac{2n}{z}J_n-J_{n-1}</math>

ven dada por

: <math>J_n=J_n(z), </math>

a [[función de Bessel]], mentres

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

resólvese con

: <math>M_n=M(n,b;z) </math>

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ón p-recursiva|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 <math>w_{t+1} = \tfrac{aw_t+b}{cw_t+d}</math> . Tal ecuación pódese resolver escribindo <math>w_t</math> como transformación non linear doutra variable <math>x_t</math> que evolúe linearmente. Así logo pódense usar métodos estándar para resolver a ecuación de diferenzas lineares en <math>x_t</math>.

== Estabilidade ==

=== Estabilidade das recorrencias lineares ===
A recorrencia linear de orde <math>d</math>,

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

ten unha [[Polinomio característico|ecuación característica]] de tipo

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

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

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

: <math>x_n=f(x_{n-1}).</math>

Esta recorrencia é localmente estable, o que significa que [[Límite dunha sucesión|converxe]] a un punto fixo <math>x^*</math> desde puntos suficientemente próximos <math>x^*</math>, se a pendente de <math>f</math> no proximidade de <math>x^*</math> é menor que a [[Un|unidade]] en valor absoluto: é dicir,

: <math>| f' (x^*) | < 1. </math>

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 de valor inicial|problema do valor inicial]]

: <math>y'(t) = f(t,y(t)), \ \ y(t_0)=y_0,</math>

co [[método de Euler]] e un tamaño de paso <math>h</math>, calculamos os valores

: <math>y_0=y(t_0), \ \ y_1=y(t_0+h), \ \ y_2=y(t_0+2h), \ \dots</math>

coa recorrencia

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

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 ==
{{reflist|30em}} 

== Véxase tamén ==
{{Commonscat}} 
=== Bibliografía ===
* {{cita libro|first1=Paul M. | last1=Batchelder
|title=An introduction to linear difference equations
|url=https://archive.org/details/introductiontoli0000paul |year=1967
|publisher=Dover Publications
}}
* {{cita libro|first1=Kenneth S. | last1=Miller
|title=Linear difference equations
|year=1968 | publisher=W. A. Benjamin
}}
* {{cita libro|first1=Jay P. | last1=Fillmore | first2=Morris L. | last2=Marx
|title=Linear recursive sequences | journal= SIAM Rev. | volume=10|number=3
|pages=324–353 | jstor=2027658| year=1968}}
* {{cita libro| first1=Alfred | last1=Brousseau
|title=Linear Recursion and Fibonacci Sequences
|year=1971
|publisher=Fibonacci Association
|url=http://www.fq.math.ca/linear.html
}}
* [[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.&nbsp;62–90.
*{{cita libro| first1=Ronald L. | last1=Graham |
first2=Donald E. | last2=Knuth
|first3=Oren | last3=Patashnik
|title=Concrete Mathematics: A Foundation for Computer Science
|edition=2
|publisher=Addison-Wesley
|year=1994 |isbn=0-201-55802-5
}}
*{{cita libro
 |year        = 2010
 |url         = http://eu.wiley.com/WileyCDA/WileyTitle/productCd-EHEP000338.html
 |first1      = Walter
 |last1       = Enders
 |title       = Applied Econometric Times Series
 |edition     = 3
 |archive-url  = https://web.archive.org/web/20141110221941/http://eu.wiley.com/WileyCDA/WileyTitle/productCd-EHEP000338.html
 |archive-date = 2014-11-10
}}
*{{cita libro| first1=Paul | last1=Cull | first2=Mary | last2=Flahive|author2-link= Mary Flahive
|first3=Robbie | last3=Robson
|title=Difference Equations: From Rabbits to Chaos
|title-link= Difference Equations: From Rabbits to Chaos
|publisher=Springer | year=2005 | isbn=0-387-23234-6 }} chapter 7.
* {{cita libro| first1=Ian | last1=Jacques
|title=Mathematics for Economics and Business
| url=https://archive.org/details/mathematicsforec00jacq|edition=Fifth
|publisher=Prentice Hall
|year=2006
|isbn=0-273-70195-9
|pages=[https://archive.org/details/mathematicsforec00jacq/page/n561 551]–568
}} Chapter 9.1: Difference Equations.
* {{cita libro| first1=Tang | last1=Minh | first2=Tan | last2=Van To | title=Using generating functions to solve linear inhomogeneous recurrence equations | pages=399–404 | url=http://www.wseas.us/e-library/conferences/2006lisbon/papers/517-481.pdf | year=2006 | work=Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06 | access-date=2014-08-07 | archive-date=2016-03-04 | archive-url=https://web.archive.org/web/20160304035925/http://www.wseas.us/e-library/conferences/2006lisbon/papers/517-481.pdf }}
* {{cita libro| first1=Andrei D. | last1=Polyanin
|title=Difference and Functional Equations: Exact Solutions
|url=http://eqworld.ipmnet.ru/en/solutions/fe.htm}} at EqWorld - The World of Mathematical Equations.
* {{cita libro| first1=Andrei D. | last1=Polyanin
|title=Difference and Functional Equations: Methods
|url=http://eqworld.ipmnet.ru/en/education/edu-fe.htm}} at EqWorld - The World of Mathematical Equations.
*{{cita libro | first1= Xiang-Sheng | last1=Wang
| first2=Roderick | last2=Wong
|title= Asymptotics of orthogonal polynomials via recurrence relations
|journal =  Anal. Appl. | year=2012 | volume=10 | number=2
|pages=215–235 | doi=10.1142/S0219530512500108 
|arxiv=1101.4371
}}
=== 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 ===
* {{springer|title=Recurrence relation|id=p/r080150}}
* {{MathWorld | urlname= RecurrenceEquation | title= Recurrence Equation}}
* {{cite web |title= OEIS Index Rec|url=http://oeis.org/wiki/Index_to_OEIS:_Section_Rec}} [[OEIS]] miles de recorrencias lineares, ordenadas por orde e sinatura.
* [https://www.fq.math.ca/list-of-issues.html Fibonacci Quarterly] publicación con máis de 60 anos de artigos sobre recorrencias (en aberto excluíndo os últimos 5 anos).


{{control de autoridades}}
[[Categoría:Combinatoria]]
[[Categoría:Álxebra]]
[[Categoría:Teoría de números]]
[[Categoría:Wikipedia:Páxinas con traducións non revisadas]]