Równanie rekurencyjne rzędu II

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Ewa :)
Użytkownik
Użytkownik
Posty: 27
Rejestracja: 27 paź 2007, o 19:19
Płeć: Kobieta
Lokalizacja: Żory
Podziękował: 5 razy

Równanie rekurencyjne rzędu II

Post autor: Ewa :) »

Mam zagadnienie, które muszę opracować wraz z przykładem, brzmi ono rozwiązanie równania rekurencyjnego rzędu drugiego. Mógłby ktoś podrzucić linka z czymś interesującym , lub samemu napisać cokolwiek na ten temat. Byłabym niezmiernie wdzięczna.
szw1710

Równanie rekurencyjne rzędu II

Post autor: szw1710 »

Jako przykład proponuję znalezienie wyrazu ogólnego ciągu Fibonacciego określonego rekurencyjnie w postaci

\(\displaystyle{ a_1=a_2=1,\\
a_{n+2}=a_{n+1}+a_n,\qquad n\geqslant 1}\)


Przenosimy wszystko na lewo:

\(\displaystyle{ (*)\quad a_{n+2}-a_{n+1}-a_n=0}\)

i zastępujemy równaniem charakterystycznym (zwykłym równaniem kwadratowym)

\(\displaystyle{ r^2-r-1=0}\)

którego rozwiązania to

\(\displaystyle{ r_1=\frac{1-\sqrt{5}}{2},\quad r_2=\frac{1+\sqrt{5}}{2}}\)

Dowodzi się, że ciąg \(\displaystyle{ (a_n)}\) spełnia równanie rekurencyjne (*) wtedy i tylko wtedy, gdy

\(\displaystyle{ a_n=\alpha r_1^n+\beta r_2^n}\)

Wartości współczynników \(\displaystyle{ \alpha,\beta}\) łatwo wyznaczyć w oparciu o warunki początkowe \(\displaystyle{ a_1=a_2=1.}\)

Opisuję tylko stronę techniczną rozwiązania takiego równania. Wiele lat temu (ponad 20) był o takich równaniach artykuł w czasopiśmie dla nauczycieli "Matematyka", ale nie pamiętam numeru, niestety. Jednakże powinnaś coś o takich rekurencjach znaleźć w podręcznikach matematyki dyskretnej. Spróbuj przeszukać Internet. Chodzi o zgłębienie teorii, bo tu na wykład mało miejsca i czasu.
ODPOWIEDZ