Równanie rekurencyjne

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

Rozwiązanie rekursji

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, 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={1+\sqrt{5}\over 2}; r_2={1-\sqrt{5}\over 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={1\over \sqrt{5}}; B=-{1\over \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