Definiția. Se spune că o secvență este recurentă dacă pentru unele k și toate n o relație a formei
unde coeficienții constanți pi; i = 1; 2; ...; k nu depind de n.
se numește polinomul caracteristic pentru secvența reciprocă.
se numesc relații omogene de recurență liniară.
Din formula (15) găsim termenul general, pentru aceasta este suficient să găsim funcția de generare a funcției de secvență. Introducem un polinom auxiliar și luăm în considerare produsul și gradul C (t) nu depășește k-1, deoarece coeficienții lui t n + k, k = 0; 1; ... vor fi zero în virtutea ecuației (15). Fie ca ecuația caracteristică (14) să aibă rădăcini simple (pot fi multiple), adică admite o descompunere a formularului. apoi,
Funcția caracteristică poate fi reprezentată în formă
Se știe că, atunci și, în consecință. (17)
Formula (17) dă extinderea funcției de generare a secvenței. Pentru a găsi formula de termen general, este necesar să găsim coeficienții pentru t n în expansiune (17).
Example1. Găsiți termenul general al secvenței care satisface relația de recurență.
Soluția. Rescriim relația originală de recurență în forma (15)
Astfel, polinomul caracteristic L (t) are forma
Folosind metoda coeficienților nedeterminate, obținem
Metode pentru găsirea unei soluții generale a relațiilor de recurență:
1. Dacă secvența de întoarcere (13) este complet determinată de atribuirea primilor ei termeni k, atunci
.
2. Dacă t este o rădăcină a polinomului caracteristic (14), atunci secvența satisface (13), atunci.
3. Dacă t1; t2; ...; tk sunt rădăcini simple (non-multiple) ale polinomului caracteristic (14), atunci soluția generală a relației de recurență (13) are forma
4. Dacă există o rădăcină a polinomului (14) al multiplicității, atunci soluția generală a relației de recurență (13) are forma
unde ci, j = 1; 2; ...; r; j = 1; ...; - constante arbitrare, r - numărul de rădăcini multiple.
Exemplul 2. Se găsește soluția generală pentru exemplul 1.
Soluția. Polinomul caracteristic are rădăcini t1 = 1; t2 = 3, apoi cu formula (18) pe care o obținem.
Exemplu 3. Rezolva relația de recurență neomogenă.