Znaleźć rozwiązanie ogólne równania rekurencyjnego

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
laki_me
Użytkownik
Użytkownik
Posty: 22
Rejestracja: 2 kwie 2009, o 15:43
Płeć: Mężczyzna
Podziękował: 4 razy

Znaleźć rozwiązanie ogólne równania rekurencyjnego

Post autor: laki_me »

Treść jak w temacie
a) \(\displaystyle{ a_{n} = 3a_{n-1} - 2a_{n-2}+ 2^{n}}\)
b) \(\displaystyle{ a_{n} = 2a_{n-1} + 7n^{2}}\)
c \(\displaystyle{ a_{n} = 3a_{n-1} + 4n, n > 0; a_{0} = 1}\)
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

Znaleźć rozwiązanie ogólne równania rekurencyjnego

Post autor: Dumel »

b)
\(\displaystyle{ a_n=2a_{n-1}+7n^2=4a_{n-2}+14(n-1)^2+7n^2=...=7(n^2+2(n-1)^2+...+2^{n-1} (n-(n-1))^2}\)
pozbywamy się nawiasów i liczymy:
\(\displaystyle{ 7n^2(1+2+4+...+2^{n-1})=7n^2(2^n-1)}\)

\(\displaystyle{ 14n \sum_{k=1}^{n-1}2^k \cdot k}\) - tutaj rozważ funkcję \(\displaystyle{ f(x)= \sum_{k=1}^{n-1}2^kx^k=2x \cdot \frac{1-(2x)^{n-1}}{1-2x}}\) i policz jej pochodną na dwa sposoby, podstawiając na końcu \(\displaystyle{ x=1}\). nie chce mi się tego liczyć, jeśli masz wątpliwości jak to zrobić zobacz tutaj: 137208.htm

\(\displaystyle{ 7 \sum_{k=1}^{n-1}2^k \cdot k^2}\) - to chyba można policzyć podobnie jak poprzednie, ale rozpatrując funkcję dwóch zmiennych \(\displaystyle{ f(x,y)= \sum_{k=1}^{n-1}2^kx^ky^k}\)
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Znaleźć rozwiązanie ogólne równania rekurencyjnego

Post autor: xiikzodz »

Zacznijmy od c)

\(\displaystyle{ a_n=3a_{n-1}+4n}\), skąd \(\displaystyle{ a_1=7, a_2=29}\)

Oznaczmy:

\(\displaystyle{ b_n=a_{n+1}-a_n}\) dla \(\displaystyle{ n=0,1,...}\), czyli \(\displaystyle{ b_0=6, b_1=22}\)

i rozważmy dwie równości, obie definiujące \(\displaystyle{ a_n}\):

\(\displaystyle{ a_{n+1}=3a_n+4(n+1)}\)
\(\displaystyle{ a_n=3a_{n-1}+4n}\)

Odejmujemy od pierwszej drugą otrzymując:

\(\displaystyle{ b_n=3b_{n-1}+4}\)

To można łatwo, ale dla treningu zastosujmy tę metodę ponownie. Oznaczmy \(\displaystyle{ c_n=b_{n+1}-b_n}\), czyli \(\displaystyle{ c_0=16}\).

Wówczas po odjęciu stronami podobnie, jak poprzednio mamy:

\(\displaystyle{ c_n=3c_{n-1}}\)

czyli

\(\displaystyle{ c_n=16\cdot 3^n}\).

Teraz wystarczy odwrócić rachunki:

\(\displaystyle{ b_n=b_0+c_0+c_1+...+c_{n-1}=6+16\cdot(1+3+...+3^{n-1})=6+16\cdot\frac{3^n-1}{2}=8\cdot 3^n-2}\)

\(\displaystyle{ a_n=a_0+b_0+b_1+...+b_{n-1}=1+8\cdot(1+3+...+3^{n-1}) -2n=4\cdot 3^n-2n-3}\).

To jest miła metoda, bo całkiem elementarna - na poziomie arytmetyki nauczania początkowego - za to bardzo mocna, bo stoi za nią silna teoria w gruncie rzeczy. Zastosujmy więc ją do punktu b):

\(\displaystyle{ a_n=2a_{n-1}+7n^2}\)

Oznaczamy \(\displaystyle{ b_n=a_{n+1}-a_n}\), czyli \(\displaystyle{ b_0=a_0+7}\)

\(\displaystyle{ a_{n+1}=2a_n+7(n+1)^2}\)
\(\displaystyle{ a_n=2a_{n-1}+7n^2}\)

po odjęciu równań:

\(\displaystyle{ b_n=2b_{n-1}+7\cdot(2n+1)}\)

Kolejno niech \(\displaystyle{ c_n=b_{n+1}-b_n}\) i odejmujemy równania:

\(\displaystyle{ b_{n+1}=2b_n+7\cdot(2n+3)}\)
\(\displaystyle{ b_n=2b_{n-1}+7\cdot(2n+1)}\)

otrzymując:

\(\displaystyle{ c_n=2c_{n-1}+14}\).

W końcu niech \(\displaystyle{ d_n=c_{n+1}-c_n}\) skąd:

\(\displaystyle{ d_n=2d_{n-1}}\)

czyli

\(\displaystyle{ d_n=d_0\cdot 2^n}\).

Pozostaje wyznaczyć \(\displaystyle{ d_0}\), czyli wcześniej również \(\displaystyle{ c_0,c_1,b_0,b_1,b_2,a_1,a_2,a_3}\) i rachunki odwrócić:

\(\displaystyle{ c_n=c_0+d_0+...+d_{n-1}}\)

\(\displaystyle{ b_n=b_0+c_0+...+c_{n-1}}\)

\(\displaystyle{ a_n=a_0+b_0+...+b_{n-1}}\)

do czego wystarczy umiejętność sumowania postępów geometrycznych.

Skoro dobrze idzie, możemy zająć się a). Metoda... ta sama. Oznaczmy:

\(\displaystyle{ b_n=a_{n+1}-2a_n}\).

Tym razem więc odwracamy rachunki zgodnie z:

\(\displaystyle{ a_n=2^na_0+2^{n-1}b_0+2^{n-2}b_1+...+b_{n-1}}\)

Odejmujemy stronami równania:

\(\displaystyle{ a_{n+1} = 3a_n - 2a_{n-1}+ 2^{n+1}}\)
\(\displaystyle{ 2a_n=6a_{n-1}-4a_{n-2}+2^{n+1}}\)

otrzymując:

\(\displaystyle{ b_n=3b_{n-1}-2b_{n-2}}\).

Do tego równania stosujemy np. metodę z wielomianem charakterystycznym, tu wygląda on tak:

\(\displaystyle{ x^2-3x+2}\)

czyli jego pierwiastki to \(\displaystyle{ 1,2}\) i postać ogólna \(\displaystyle{ b_n}\):

\(\displaystyle{ b_n=\alpha+\beta\cdot 2^n}\)

No i teraz oczywiście stosujemy:

\(\displaystyle{ a_n=2^na_0+2^{n-1}b_0+...+b_{n-1}}\)

co po zastosowaniu umiejętności sumowania postępów geometrycznych natychmiast daje wynik.

(Podejrzewam, że w tym zadaniu chodziło o zastosowanie funkcji tworzących. Po pierwsze miło jest zobaczyć rozwiązanie elementarne, a po drugie mając te rozwiązania łatwo znaleźć stosowne funkcje tworzące.)
laki_me
Użytkownik
Użytkownik
Posty: 22
Rejestracja: 2 kwie 2009, o 15:43
Płeć: Mężczyzna
Podziękował: 4 razy

Znaleźć rozwiązanie ogólne równania rekurencyjnego

Post autor: laki_me »

prawdę mówiąc nie rozumiem skąd wziąłeś to \(\displaystyle{ a_{n+1}=3a_n+4(n+1)}\)
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

Znaleźć rozwiązanie ogólne równania rekurencyjnego

Post autor: Dumel »

lol przecież skoro \(\displaystyle{ a_n=3a_{n-1}+4n}\) to jak n zastąpimy przez n+1 to dostaniemy \(\displaystyle{ a_{n+1}=3a_{n}+4(n+1)}\)
i jeszcze radzę patrzeć czasem na płeć
ODPOWIEDZ