Rekurencja III rzędu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Bartom
Użytkownik
Użytkownik
Posty: 67
Rejestracja: 5 gru 2015, o 12:39
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 21 razy

Rekurencja III rzędu

Post autor: Bartom »

\(\displaystyle{ a _{0}=3,a _{1}=10, a_{2}=11 , a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}-3}\)

Obliczam równanie charakterystyczne, wyliczam pierwiastki \(\displaystyle{ r_{1}=1,r_{2}=2,r_{3}=-2}\)
Ale jak wygląda ogólna postać ciągu? Po prostu \(\displaystyle{ a_{n}=A+B2 ^{n}+C(-2)^{n}}\)?
Ta -3 w rekurencji przysparza mi problemów. Bo w końcu \(\displaystyle{ -3=-3 \cdot (1)^{n}}\), czyli podstawa potęgi jest równa jednemu pierwiastkowi charakterystycznemu... Co dalej?
Ostatnio zmieniony 22 cze 2017, o 21:28 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
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

Rekurencja III rzędu

Post autor: Premislav »

Ta rekurencja nie jest liniowa, właśnie przez to \(\displaystyle{ -3}\), więc postać rozwiązania ogólnego nie będzie dokładnie taka jak napisałeś. Można to rozwiązać z użyciem funkcji tworzących lub metody przewidywania, za którą nie przepadam, ale która często się pojawia, a tu akurat jest łatwa do zastosowania. Metodą przewidywania znajdujesz rozwiązanie szczególne tej rekurencji, a rozwiązanie ogólne to będzie suma tego rozwiązania szczególnego i rozwiązania rekurencji jednorodnej
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}}\)
Tutaj można przewidzieć rozwiązanie szczególne w postaci \(\displaystyle{ x_n=c\cdot n}\) gdzie \(\displaystyle{ c}\) to stała. Po podstawieniu do zależności
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}-3}\) za \(\displaystyle{ a_n=x_n}\) mamy:
\(\displaystyle{ c n=c(n-1)+4c(n-2)-4c(n-3)-3}\)
czyli
\(\displaystyle{ 3c-3=0}\),
a więc \(\displaystyle{ c=1}\), czyli rozwiązanie szczególne rekurencji niejednorodnej jest postaci
\(\displaystyle{ x_n=n}\)
Natomiast rozwiązanie ogólne rekurencji jednorodnej
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}}\)
ma postać
\(\displaystyle{ A+B\cdot 2^n+C\cdot (-2)^n}\)
Zatem rozwiązanie ogólne rekurencji niejednorodnej:
\(\displaystyle{ a_n=A+B\cdot 2^n+C\cdot (-2)^n+x_n=A+B\cdot 2^n+C\cdot (-2)^n+n}\)
Teraz podstawiasz dane warunki początkowe i masz układ równań:
\(\displaystyle{ \begin{cases} a_0=A+B\cdot 2^0+C\cdot (-2)^0+0\\a_1=A+B\cdot 2^1+C\cdot (-2)^1+1 \\ a_2=A+B\cdot 2^2+C\cdot (-2)^2+2\end{cases}}\)
rozwiązujesz ten układ równań ze względu na \(\displaystyle{ A, B, C}\)
i koniec.
Bartom
Użytkownik
Użytkownik
Posty: 67
Rejestracja: 5 gru 2015, o 12:39
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 21 razy

Rekurencja III rzędu

Post autor: Bartom »

Ciekawe rozwiązanie, aczkolwiek metoda funkcji tworzących jest tu odgórnie narzucona...
Mógłbyś mi przybliżyc rozwiązanie za jej pomocą?
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

Rekurencja III rzędu

Post autor: Premislav »

Z użyciem funkcji tworzących to byłoby tak:
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}-3\a_{n+3}=a_{n+2}+4a_{n+1}-4a_n-3\ sum_{n=0}^{ infty }a_{n+3} z^n= sum_{n=0}^{ infty }left( a_{n+2}+4a_{n+1}-4a_n-3
ight) z^n\ frac{1}{z^3} sum_{n=0}^{ infty }a_{n+3}z^{n+3}= frac{1}{z^2} sum_{n=0}^{ infty }a_{n+2}z^{n+2}+ frac{4}{z} sum_{n=0}^{ infty }a_{n+1}z^{n+1}-4 sum_{n=0}^{ infty }a_n z^n -3 sum_{n=0}^{ infty }z^n\ sum_{n=0}^{ infty }a_{n+3}z^{n+3}=z sum_{n=0}^{ infty }a_{n+2}z^{n+2}+4z^2 sum_{n=0}^{ infty }a_{n+1}z^{n+1}-4 z^3sum_{n=0}^{ infty }a_n z^n -3z^3 sum_{n=0}^{ infty }z^n}\)

Niech teraz \(\displaystyle{ G(z)=sum_{n=0}^{ infty }a_n z^n}\)
Wówczas mamy
\(\displaystyle{ sum_{n=0}^{ infty }a_{n+3}z^{n+3}=G(z)-a_0-a_1 z-a_2 z^2\sum_{n=0}^{ infty }a_{n+2}z^{n+2}=G(z)-a_0-a_1 z\sum_{n=0}^{ infty }a_{n+1}z^{n+1}=G(z)-a_0}\)
Ponadto oczywiście mamy
\(\displaystyle{ sum_{n=0}^{ infty }z^n=frac{1}{1-z}}\)
Zatem:
\(\displaystyle{ G(z)-a_0-a_1 z-a_2 z^2=zleft(G(z)-a_0-a_1 z
ight) +4z^2left( G(z)-a_0
ight)-4z^3G(z) - frac{3z^3}{1-z}}\)

Wyliczasz z tego \(\displaystyle{ G(z)}\), traktując to jak równanie z niewiadomą \(\displaystyle{ G(z)}\), podstawiasz z danych
\(\displaystyle{ a _{0}=3,a _{1}=10, a_{2}=11}\)
no a potem wykonujesz rozkład na ułamki proste: 298450.htm
i rozwijasz te ułamki w szeregi potęgowe.
Bartom
Użytkownik
Użytkownik
Posty: 67
Rejestracja: 5 gru 2015, o 12:39
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 21 razy

Rekurencja III rzędu

Post autor: Bartom »

Wspaniale, dziękuję bardzo
domel1234
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 4 cze 2017, o 23:38
Płeć: Mężczyzna
Lokalizacja: Wrocław

Re: Rekurencja III rzędu

Post autor: domel1234 »

Jest dużo prostszy sposób. Od wyrazu \(\displaystyle{ a _{n+1}}\) odejmujesz wyraz \(\displaystyle{ a _{n}}\).
\(\displaystyle{ -3}\) się redukuje i masz normalną liniową rekurencję, którą możesz rozwiązać poprzez zwykłe podstawienie \(\displaystyle{ a _{n} = r ^{n}}\).
ODPOWIEDZ