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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fc6a5185f932b78c75e5a82bed82fb3ad8f3961)
gdzie dane jest
Załóżmy, że ma ono rozwiązanie postaci
Podstawiając otrzymujemy:
![{\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c81b3852c0f3be11e0a24dce7ef6919bd5122ac5)
Dzieląc przez
![{\displaystyle r^{2}=Ar+B,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/086c728d656158a8652cdcaebff9bdac5d8f3d33)
![{\displaystyle r^{2}-Ar-B=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a27139fe824c0e0deedfc28dad45a646fa0e3f9)
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8575e7f0606d9241bfc2b23b605dc1a4ff3fca82)
Jeżeli natomiast równanie charakterystyczne ma pierwiastek podwójny, to
![{\displaystyle a_{n}=(C+Dn)r_{1}^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9b256545ba4bed9c1d81ea95ccf3201ccfa4917)
i
są dowolnymi stałymi a
i
są pierwiastkami równania charakterystycznego. Jeżeli dane jest
i
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6814517a76f1ecf071a4bab5ecce726f03695013)
Warunki początkowe:
![{\displaystyle a_{0}=0,\quad a_{1}=1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa1a9d2cd784adb1a91f63dccb2f179ddf0e10f7)
Równanie charakterystyczne ma następującą postać:
![{\displaystyle r^{2}-r-1=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b03dcf9c64434e8ee10ec2f88f0d1223933c1764)
Pierwiastki tego równania są następujące:
![{\displaystyle r_{1}={\frac {1+{\sqrt {5}}}{2}};\quad r_{2}={\frac {1-{\sqrt {5}}}{2}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3730caf5e0735cff0507505a6d2bb40778a16e73)
Pierwiastki są różne, zatem:
![{\displaystyle a_{n}=Ar_{1}^{n}+Br_{2}^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eda2196d346cf9b4034b73c8d2668576bd022817)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/353a814ebea0639db1899cd95cf8a11f15714bf3)
Z rozwiązania tego układu wynika:
![{\displaystyle A={\frac {1}{\sqrt {5}}};\quad B=-{\frac {1}{\sqrt {5}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e68d99b4e6187b12b4b8166747faf8b83e7739f)
Co po podstawieniu
i
do wzoru na
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ba26542a3145289fa612b48b4def2d705b1a498)
Zobacz też
Kontrola autorytatywna (ciąg):
- LCCN: sh85037879
- GND: 4012264-5
- BNCF: 2923
- NKC: ph119449
- J9U: 987007553021405171
Encyklopedie internetowe:
- Britannica: topic/recurrence-relation
- БРЭ: 3504917