Równania rekurencyjne

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
zuzka_kotek
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 23 lut 2016, o 20:45
Płeć: Kobieta
Lokalizacja: Gdańsk
Podziękował: 4 razy

Równania rekurencyjne

Post autor: zuzka_kotek »

Czy ktoś mógłby wytłumaczyć mi w miarę prosty sposób(tak krok po kroku) jak rozwiązuje się tego typu zadania:
1)Znajdź rozwiązanie ogólne dla każdego z poniższych równań rekurencyjnych
\(\displaystyle{ a_{n+2}=2a_{n+1}+3a_{n}}\)
2)Znajdź rozwiązanie szczególne dla każdego z poniższych równań rekurencyjnych:
\(\displaystyle{ c_{1}=7, c_{2}=10; c_{n+2}=2c_{n+1}-4c_{n}}\)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Równania rekurencyjne

Post autor: Premislav »

1) istnieje co najmniej kilka metod, np. metoda równania charakterystycznego (które bierze się z potęgowania macierzy) czy metoda funkcji tworzących.

Metoda funkcji tworzących:
\(\displaystyle{ a_{n+2}=2a_{n+1}+3a_{n}\\ \sum_{n=0}^{ \infty }a_{n+2}x^{n}= 2\sum_{n=0}^{ \infty }a_{n+1}x^{n}+3\sum_{n=0}^{ \infty }a_{n}x^{n}\\ \frac{1}{x^{2}} \sum_{n=0}^{ \infty }a_{n+2}x^{n+2}= \frac{2}{x} \sum_{n=0}^{ \infty }a_{n+1}x^{n+1}+3 \sum_{n=0}^{ \infty }a_{n}x^{n}}\)
Oznaczmy teraz \(\displaystyle{ S= \sum_{n=0}^{ \infty }a_{n}x^{n}}\). Wtedy powyższe można zapisać tak:
\(\displaystyle{ \frac{1}{x^{2}}(S-a_{1}x-a_{0})= \frac{2}{x}(S-a_{0})+3S\\ S= \frac{ \frac{a_{1}}{x}+ \frac{a_{0}}{x^{2}}- \frac{a_{0}}{2x} }{ \frac{1}{x^{2}}- \frac{2}{x}-3 }= \frac{2xa_{1}+2a_{0}-xa_{0}}{2-4x-6x^{2}}}\)
Dalej rozkładasz
\(\displaystyle{ \frac{2xa_{1}+2a_{0}-xa_{0}}{2-4x-6x^{2}}}\) na ułamki proste i rozwijasz w szeregi (korzystając ze wzorów na sumę zbieżnego szeregu geometrycznego i pochodną tejże sumy). Współczynnik stojący w rozwinięciu przy \(\displaystyle{ x^{n}}\) to będzie \(\displaystyle{ a_{n}}\)... Widzimy tutaj, że do jednoznacznego rozwiązania potrzebujemy danych wartości \(\displaystyle{ a_{0}}\) i \(\displaystyle{ a_{1}}\), co nie powinno być zaskoczeniem.-- 11 kwi 2016, o 17:09 --Metodę równania charakterystycznego masz wszędzie opisaną, wystarczy wpisać "rekurencja liniowa równanie charakterystyczne" czy coś takiego, a przyszło mi do głowy jeszcze coś innego (tylko ten sposób nie jest chyba zbyt uniwersalny).
Mamy równanie
\(\displaystyle{ a_{n+2}=2a_{n+1}+3a_{n}}\)
Dodajmy stronami \(\displaystyle{ a_{n+1}}\), a otrzymamy \(\displaystyle{ a_{n+2}+a_{n+1}=3(a_{n+1}+a_{n})}\). Jeżeli teraz oznaczymy \(\displaystyle{ b_{n}=a_{n+1}+a_{n}}\), to \(\displaystyle{ b_{n+1}=3b_{n}}\), zatem ciąg \(\displaystyle{ (b_{n})}\) jest geometryczny. Jeżeli znamy \(\displaystyle{ a_{0}}\) i \(\displaystyle{ a_{1}}\)(a więc także \(\displaystyle{ b_{0}=a_{0}+a_{1}}\)), to stąd łatwo dostaniemy \(\displaystyle{ b_{n}=3^{n}b_{0}=3^{n}(a_{0}+a_{1})}\), czyli \(\displaystyle{ a_{n}+a_{n+1}=3^{n}(a_{0}+a_{1})}\)
Dalej: \(\displaystyle{ a_{n+1}=a_{n+1}+a_{n}-(a_{n}+a_{n-1})+a_{n-1}+a_{n-2}-...}\)
i tak dalej, dla przykładu
\(\displaystyle{ a_{4}=a_{4}+a_{3}-(a_{3}+a_{2})+a_{2}+a_{1}-(a_{1}+a_{0})+a_{0}}\)
Można to zwinąć ze wzoru na sumę początkowych wyrazów ciągu geometrycznego, tylko trzeba dobrze policzyć, ile jest tych wyrazów i pamiętać o zmianie indeksów.
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Równania rekurencyjne

Post autor: Mariusz M »

Równanie charakterystyczne też nie jest zbyt uniwersalne spróbuj rozwiązać nim równanie na liczby Catalana czy równanie o zmiennych współczynnikach

Mamy też takie równania jak równanie na liczby Bernoulliego, Bella itp
ODPOWIEDZ