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

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

gdzie dane jest ${\displaystyle A,B.}$

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

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

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

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

${\displaystyle 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

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

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

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

${\displaystyle C}$ i ${\displaystyle D}$ są dowolnymi stałymi a ${\displaystyle r_{1}}$ i ${\displaystyle r_{2}}$ są pierwiastkami równania charakterystycznego. Jeżeli dane jest ${\displaystyle a_{1}}$ i ${\displaystyle 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:

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

Warunki początkowe:

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

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

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

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

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

Pierwiastki są różne, zatem:

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

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

${\displaystyle {\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:

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

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

${\displaystyle 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