En matemàtiques, una relació de recurrència és una equació que defineix recursivament una successió o una matriu multidimensional de valors, un cop es donen un o més termes inicials; cada terme següent de la seqüència o matriu es defineix com una funció dels termes anteriors.
De vegades, el terme equació en diferències (i als efectes d'aquest article) fa referència a un tipus específic de relació de recurrència, que relaciona diferents successions, sent una d'elles una successió desconeguda. No obstant això, sovint s'utilitza «equació en diferències» per referir-se a qualsevol relació de recurrència.
Són similars a les equacions diferencials, substituint les funcions per successions. Per a la seva resolució sol utilitzar el mètode de la transformada Z
Definició Una relació de recurrència és una equació que expressa cada element d'una successió en funció dels elements anteriors. Més exactament, en el cas que només hi hagi l'element immediatament precedent, una relació de recurrència té la forma
on
és una funció, on és un conjunt al qual han de pertànyer els elements d'una seqüència. Per , això defineix una seqüència única amb com a primer element, anomenat valor inicial.
És fàcil modificar la definició per obtenir seqüències a partir del terme de l'índex 1 o superior.
Això defineix la relació de recurrència de primer ordre. Té forma la relació de recurrència d'ordre k
on és una funció que inclou k elements consecutius de la seqüència. En aquest cas, es necessiten k valors inicials per definir una seqüència.
Exemples Factorial El factorial es defineix per la relació de recurrència
i la condició inicial
Mapa logístic Un exemple de relació de recurrència és el mapa logístic:
amb una constant r donada; donat el terme inicial x0 cada terme posterior es determina per aquesta relació
Resoldre una relació de recurrència significa obtenir una solució en forma tancada, una funció no-recursiva de n.
Nombres de Fibonacci La recurrència d'ordre dos satisfeta pels nombres de Fibonacci és l'arquetip d'una relació de recurrència lineal homogènia amb coeficients constants (vegeu més avall). La seqüència de Fibonacci es defineix mitjançant la recurrència
amb condicions inicials
Explícitament, la recurrència produeix les equacions
etc.
Obtenim la seqüència de números de Fibonacci, que comença
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
La recurrència es pot resoldre mitjançant mètodes descrits a continuació, obtenint la fórmula de Binet, que inclou potències de les dues arrels del polinomi característic t² = t + 1; la funció generadora de la seqüència és la funció racional
Coeficients binomials Un senzill exemple de relació de recurrència multidimensional ve donat pels coeficients binomials , que compten el nombre de maneres de seleccionar k elements entre un conjunt de n elements. Es poden calcular mitjançant la relació de recurrència
amb les condicions inicials .
Utilitzant aquesta fórmula per calcular els valors de tots els coeficients binomials es genera una matriu infinita anomenada triangle de Pascal. Els mateixos valors també es poden calcular directament mitjançant una fórmula diferent que no és una recurrència, però que requereix multiplicació i no només una addició per calcular:
Relacions amb equacions en diferències estretament definides Donada una successió ordenada de nombres reals:
La primera diferència es defineix com
La segona diferència es defineix com
que es pot simplificar a
De manera general, la diferència k-èsima de la successió an, denotada , es defineix recursivament com
(La seqüència i les seves diferències estan relacionades per una transformada binomial). La definició més restrictiva de l'equació en diferències és una equació composta per an i les seves kèsimes diferències. (Una definició més àmpliament utilitzada tracta «equació en diferència» com a sinònim de «relació de repetició». Vegeu per exemple l'equació de racional en diferències i l'equació de matriu en diferències).
De fet, es veu fàcilment que,
Així, una equació en diferència es pot definir com una equació que implica an, an-1, an-2 , etc. (o de manera equivalent, an, an+1, an+2, etc.)
Com que les equacions en diferències són una forma molt freqüent de recurrència, alguns autors utilitzen de manera intercanviable els dos termes. Per exemple, l'equació en diferències
equival a la relació de recurrència
Així, es pot resoldre moltes relacions de recurrència tornant a escriure-les com a equacions en diferències i, a continuació, resoldre l'equació en diferències, de manera analògica a com es resolen les equacions diferencials ordinàries. No obstant això, els nombres d'Ackermann són un exemple de relació de recurrència que no es correspon amb una equació en diferències, molt menys en la solució a una equació diferencial (Vegeu càlcul d'escala de temps per a una relacióde la teoria de les equacions en diferències amb la de les equacions diferencials).
Les equacions en sumes es relacionen amb equacions en diferències, ja que les equacions integrals es relacionen amb les equacions diferencials.
De successions a quadrícules Les relacions de recurrència d'una sola variable o unidimensionals són sobre seqüències (és a dir, funcions definides a les quadrícules unidimensionals). Les relacions de recurrència multi-variables o n-dimensionals es refereixen a quadrícules n-dimensionals. Les funcions definides a les n-quadrícules també es poden estudiar amb equacions en diferències parcials.
Resolució Resolució de relacions homogènies de recurrència lineal amb coeficients constants
Arrels de polinomis característics Una recurrència lineal homogènia d'ordre d amb coeficients constants és una equació de la forma
on els d coeficients ci (per a tot i) són constants, i .
Una seqüència constant-recursiva és una seqüència que satisfà una recuerrència d'aquesta forma. Hi ha d graus de llibertat per solucionar aquesta recurrència, és a dir, els valors inicials es pot considerar que són valors, però la recurrència determina la seqüència de forma única.
Els mateixos coeficients produeixen el polinomi característic (també «polinomi auxiliar»)
les d arrels les quals tenen un paper crucial per trobar i comprendre les seqüències que satisfan la recurrència. Si les arrels r1, r₂, ... són diferents, llavors cada solució per a la recurrència pren la forma
on els ki coeficients es determinen per adaptar-se a les condicions inicials de la recurrència. Quan les mateixes arrels es produeixen diverses vegades, els termes d'aquesta fórmula corresponents a la segona i posterior ocurrències de la mateixa arrel es multipliquen augmentant les potències de n. Per exemple, si el polinomi característic es pot factoritzar com (x−r)3, amb la mateixa arrel r que es produeix tres vegades, llavors la solució prendria la forma
A més dels nombres de Fibonacci, altres seqüències constant-recursiva inclouen els nombres de Lucas i la successió de Lucas, els nombres de Jacobsthal, els nombres de Pell i, més generalment, les solucions per a l'equació de Pell.
Per a l'ordre 1, la recurrència.
té la solució an = rn amb a0 = 1 i la solució més general és an = krn amb a0 = k. El polinomi característic equivocat a zero (l'equació característica) és simplement t − r = 0.
Les solucions a aquestes relacions de recurrència d'ordre superior es troben per mitjans sistemàtics, sovint utilitzant el fet que an = rn és una solució per a la recurrència exactament quan t = r és una arrel del polinomi característic. Es pot abordar directament o utilitzant funcions generatrius (sèries formals de potències) o matrius.
Si es consiera, per exemple, una relació de recurrència de la forma
quan té una solució de la mateixa forma general que an = rn? Substituint aquesta solució estimada (ansatz) en la relació de recurrència, trobem que
ha de ser cert per a tot n > 1.
Dividint a través de rn−2, assolim que totes aquestes equacions es redueixin a la mateixa cosa:
que és l'equació característica de la relació de recurrència. Resolent r per obtenir les dues arrels λ1, λ₂: aquestes arrels es coneixen com les arrels característiques o valors propis de l'equació característica. S'obtenen diferents solucions segons la naturalesa de les arrels; Si aquestes arrels són diferents, tenim la solució general
mentre que si són idèntiques (quan A² + 4B = 0), tenim
Aquesta és la solució més general; les dues constants C i D es poden triar en funció de dues condicions inicials a0 i a1 per produir una solució específica.
En el cas de valors propis complexos (que també generen valors complexos per als paràmetres de solució C i D), es pot eliminar l'ús de nombres complexos reescrivint la solució en forma trigonomètrica. En aquest cas podem escriure els valors propis com Aleshores es pot demostrar que
es pot reescriure com
on
Aquí E i F (o equivalentment, G i δ) són constants reals que depenen de les condicions inicials. Utilitzant
es pot simplificar la solució anterior
on a1 i a₂ són les condicions inicials, i
D'aquesta manera, no cal resoldre λ1 ni λ₂.
En tots els casos (valors propis reals diferents, valors propis reals duplicats, i valors propis complexos conjugats) l'equació és estable (és a dir, la variable convergeix a un valor fix (específicament, zero)) si i només si ambdós valors propis tenen un valor absolut inferior a 1. En aquest cas de segon ordre, es pot demostrar que aquesta condició dels valors propis és equivalent a |A| < 1 − B < 2, que equival a |B| < 1 i |A| < 1 − B.
L'equació de l'exemple anterior era homogènia, ja que no hi havia un terme constant. Si es comença amb la recurrència no-homogènia
amb el terme K constant, es pot convertir en forma homogènia de la següent manera: L'estat estacionari es troba mitjançant per la configuració bn = bn−1 = bn−2 = b*, obtenint
Lavors, la recurrència no-homogènia es pot reescriure de forma homogènia com
que es pot resoldre com abans.
La condició d'estabilitat esmentada anteriorment en termes de valors propis del cas de segon ordre continua essent vàlida per al cas general d'ordre n-èsim; l'equació és estable si i només si tots els valors propis de l'equació característica tenen un valor absolut inferior a 1.
Tenint en compte una relació de recurrència lineal homogènia amb coeficients constants de l'ordre d, fem que p(t) sigui el polinomi característic (també «polinomi auxiliar»)
de manera que cada ci correspon a cada ci en la relació de recurrència original (vegeu la forma general anterior). Suposem que λ és una arrel de p(t) amb multiplicitat r. Això vol dir que (t−λ)r divideix p(t). Les dues propietats següents contenen:
Cadascuna de les r seqüències satisfan la relació de recurrència. Qualsevol seqüència que satisfaci la relació de recurrència es pot escriure de manera única com una combinació lineal de solucions construïdes en la primera part com a varies λ en funció de totes les arrels diferents de p(t).
Com a resultat d'aquest teorema, es pot resoldre una relació de recurrència lineal homogènia amb coeficients constants de la següent manera:
1. Cercar el polinomi característic p(t). 2. Cercar les arrels de p(t) comptant la multiplicitat. 3. Escriure an com a combinació lineal de totes les arrels (comptant la multiplicitat com es mostra al teorema anterior) amb coeficients bi desconeguts.
Aquesta és la solució general a la relació de recurrència original (q és la multiplicitat de λ * ).