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=A{a}_{n-1}+B{a}_{n-2},$

gdzie dane jest $A,B.$

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

$r^n=A{r}^{n-1}+B{r}^{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=C{r}_1^n+D{r}_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,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};r_2=\frac{1-\sqrt{5}}{2}.$

Pierwiastki są różne, zatem:

$a_n=A{r}_1^n+B{r}_2^n.$

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

$\{\begin{array}{c}{a}_0=0:A+B=0,\\ a_1=1:A{r}_1+B{r}_2=1.\end{array}$

Z rozwiązania tego układu wynika:

$A=\frac{1}{\sqrt{5}};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