Równanie rekurencyjne

Równanie rekurencyjne – równanie, które definiuje ciąg w sposób rekurencyjny.

Rozwiązanie rekurencji

Jest to postać jawna (iteracyjna) równania rekurencyjnego opisującego daną rekursję.

W większości przypadków, przy zastosowaniu odpowiednio zaawansowanego aparatu algebraicznego można uzyskać dokładne rozwiązanie równania/nierówności rekurencyjnej, często są to jednak metody nieefektywne lub numerycznie niestabilne. Zazwyczaj zadowalające jest rozwiązanie asymptotyczne.

Przykład

Przykładem równania rekurencyjnego liniowego jednorodnego jest równanie postaci

$a_{n}=Aa_{n-1}+Ba_{n-2},$

gdzie dane jest $A,B.$

Załóżmy, że ma ono rozwiązanie postaci $a_{n}=r^{n}.$ Podstawiając otrzymujemy:

$r^{n}=Ar^{n-1}+Br^{n-2}.$

Dzieląc przez $r^{n-2}{:}$

$r^{2}=Ar+B,$

$r^{2}-Ar-B=0.$

Równanie to nazywamy równaniem charakterystycznym równania rekurencyjnego. W tym przypadku jest to równanie kwadratowe.

Jeżeli nie ma ono pierwiastków podwójnych, wówczas

$a_{n}=Cr_{1}^{n}+Dr_{2}^{n}.$

Jeżeli natomiast równanie charakterystyczne ma pierwiastek podwójny, to

$a_{n}=(C+Dn)r_{1}^{n}.$

$C$ i $D$ są dowolnymi stałymi a $r_{1}$ i $r_{2}$ są pierwiastkami równania charakterystycznego. Jeżeli dane jest $a_{1}$ i $a_{2}$ wówczas można łatwo ułożyć układ równań i otrzymać ich wartość.

Przykład (ciąg Fibonacciego)

Następujący przykład jest rozwiązaniem ciągu Fibonacciego:

$a_{n}=a_{n-1}+a_{n-2}.$

Warunki początkowe:

$a_{0}=0,\quad a_{1}=1.$

Równanie charakterystyczne ma następującą postać:

$r^{2}-r-1=0.$

Pierwiastki tego równania są następujące:

$r_{1}={\frac {1+{\sqrt {5}}}{2}};\quad r_{2}={\frac {1-{\sqrt {5}}}{2}}.$

Pierwiastki są różne, zatem:

$a_{n}=Ar_{1}^{n}+Br_{2}^{n}.$

Korzystając z warunków początkowych, układamy układ równań:

${\begin{cases}a_{0}=0:A+B=0,\\a_{1}=1:Ar_{1}+Br_{2}=1.\end{cases}}$

Z rozwiązania tego układu wynika:

$A={\frac {1}{\sqrt {5}}};\quad B=-{\frac {1}{\sqrt {5}}}.$

Co po podstawieniu $A$ i $B$ do wzoru na $a_{n}$ otrzymujemy tzw. wzór Bineta:

$a_{n}={\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-{\frac {1}{\sqrt {5}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}.$

Zobacz też

• twierdzenie o rekurencji uniwersalnej