Relații omogene și neomogene liniare recurență, referatelor libere, eseuri și

Definiția. Secvența se numește recurentă în cazul în care pentru unele k și tot n relația de forma

unde coeficienții constanți pi; i = 1, 2, ..., k sunt independente de n.

Se numește polinomul caracteristic pentru secvența de retur.

numita omogenă relație lineară de recurență.

De la formula (15) găsi un membru comun, este suficient pentru a găsi funcția de generare - funcția. Introducem un polinom auxiliar și ia în considerare produsul, gradul de C (t) nu depășește k-1, ... ca
Coeficienții la t n + k, k = 0, 1, ... sunt zero în virtutea ecuației (15). Să presupunem că ecuația caracteristică (14) are o rădăcini mai simple (eventual multiple), adică Acesta permite extinderea formei. apoi,

Funcția caracteristică poate fi scrisă ca

Este cunoscut faptul că de fapt și, în consecință. (17)

Ecuația (17) dă funcția generatoare de descompunere. Pentru a găsi termenul general formulei este necesară pentru a găsi coeficienții la t n în expansiune (17).

Example1. Găsiți termenul general al secvenței satisface relația de recurență.

Decizie. Rescriem relația de recurență inițială a formei (15)

Polinomul caracteristic L (t) are forma, atunci

Metoda coeficienților nedeterminați obținem

Modalități de a găsi soluția generală a relațiilor de recurenta:

1. În cazul în care secvența de retur (13) este pe deplin eepervyh membrii k opredelyaetsyazadaniem,

.
2. Dacă t este rădăcina polinomului caracteristic (14), secvența satisface relația (13), atunci.

3. În cazul în care T1; t2, ..., simplu tk (non-multiple), rădăcinile polinomului caracteristic (14), atunci soluția generală a relației de recurență (13) are forma

4. Dacă există o rădăcină polinom (14) multiplicității, soluția generală a relației de recurență (13) are forma

unde c i, j = 1, 2, ... r; j = 1; ...; - constante arbitrare, r - număr multiple rădăcini.

Exemplul 2. Găsiți soluția generală din Exemplul 1.

Decizie. Polinomul caracteristic are un t1 root = 1; t2 = 3, apoi în conformitate cu formula (18) obținem.

Exemplul 3. Pentru a rezolva recurență neuniforma.