Witam,
Na wstępie zaznaczam, że przeczesałem wyszukiwarkę, ale wśród znalezionych tematów dot. rekurencji/czynnika sumacyjnego nie znalazłem dla siebie pomocy.
Mam podać wzór zwarty \(\displaystyle{ T_n}\) dla wzoru rekurencyjnego \(\displaystyle{ a_{n+1} = 2a_n +2n +1}\)
Z powyższego wyliczyłem, że
\(\displaystyle{ T_{n+1}=2T_n+2n+1}\)
\(\displaystyle{ T_n=2T_{n-1}+2_{n-1}+1}\)
\(\displaystyle{ T_n=2T_{n-1}+2n-1}\)
I dodatkowo mam jeszcze wyliczone:
\(\displaystyle{ T_n=2T_{n-1}+2n-1=2(2T_{n-2}+2_{n-1}-1)+2n-1}\)
Wzór na czynnik sumacyjny to \(\displaystyle{ s_n = s_{n-1} \frac{a_{n-1}}{b_n}}\) dla równania \(\displaystyle{ a_n T_n = b_n T_{n-1} + c_n}\)
Nie wiem czy dobrze podstawiam...
\(\displaystyle{ a_n=1}\)
\(\displaystyle{ b_n=2}\)
\(\displaystyle{ c_n=-1}\)
Jak dalej to obliczyć? Zdaje się, że można też to zrobić inną metodą niż czynnikiem sumacyjnym, ale chyba w ten sposób najłatwiej...
Rozwiązanie rekurencji metodą czynnika sumacyjnego
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Rozwiązanie rekurencji metodą czynnika sumacyjnego
Brakuje warunku początkowego.
Co do czynnika sumacyjnego - gotowy wzór wygodniej zapisać w postaci \(\displaystyle{ s_n=\frac{a_1a_2\ldots a_{n-1}}{b_2b_3\ldots b_n}}\) (może też być dowolna wielokrotność tego ułamka). Widać więc, że w tym wypadku jest \(\displaystyle{ s_n=\frac{1}{2^{n-1}}}\), albo wygodniej: \(\displaystyle{ s_n=\frac{1}{2^n}}\). Po pomnożeniu rekurencji stronami przez \(\displaystyle{ s_n}\) i podstawieniu \(\displaystyle{ U_n=\frac{T_n}{2^{n}}}\) dostaniemy:
\(\displaystyle{ U_n-U_{n-1}=\textrm{coś tam}}\)
Wystarczy teraz zsumować tę równość po \(\displaystyle{ n}\) od \(\displaystyle{ 1}\) do \(\displaystyle{ N}\). Z lewej strony prawie wszystko się skróci, z prawej trzeba jakoś policzyć sumę "cośtamów" - i stąd dostaniemy wzór na \(\displaystyle{ U_n}\), a potem wracając do podstawienia, także na \(\displaystyle{ T_n}\).
Q.
Co do czynnika sumacyjnego - gotowy wzór wygodniej zapisać w postaci \(\displaystyle{ s_n=\frac{a_1a_2\ldots a_{n-1}}{b_2b_3\ldots b_n}}\) (może też być dowolna wielokrotność tego ułamka). Widać więc, że w tym wypadku jest \(\displaystyle{ s_n=\frac{1}{2^{n-1}}}\), albo wygodniej: \(\displaystyle{ s_n=\frac{1}{2^n}}\). Po pomnożeniu rekurencji stronami przez \(\displaystyle{ s_n}\) i podstawieniu \(\displaystyle{ U_n=\frac{T_n}{2^{n}}}\) dostaniemy:
\(\displaystyle{ U_n-U_{n-1}=\textrm{coś tam}}\)
Wystarczy teraz zsumować tę równość po \(\displaystyle{ n}\) od \(\displaystyle{ 1}\) do \(\displaystyle{ N}\). Z lewej strony prawie wszystko się skróci, z prawej trzeba jakoś policzyć sumę "cośtamów" - i stąd dostaniemy wzór na \(\displaystyle{ U_n}\), a potem wracając do podstawienia, także na \(\displaystyle{ T_n}\).
Q.
Rozwiązanie rekurencji metodą czynnika sumacyjnego
Warunek początkowy to chyba \(\displaystyle{ T_1=1}\), bo we wcześniejszym wzorze \(\displaystyle{ a_1=1}\)
Nie do końca rozumiem dlaczego \(\displaystyle{ s_n=\frac{1}{2^{n-1}}}\) - to "n-1 do kwadratu" jest wzięte z \(\displaystyle{ a_{n-1}}\) we wzorze \(\displaystyle{ s_n=\frac{a_1a_2\ldots a_{n-1}}{b_2b_3\ldots b_n}}\) ? I dlaczego potem można to skrócić do \(\displaystyle{ s_n=\frac{1}{2^n}}\) ?
Pomnożenie rekurencji przez \(\displaystyle{ s_n}\) wyglądałoby tak?:
\(\displaystyle{ T_n * \frac{1}{2^n} = 2T_{n-1}+2n-1 * \frac{1}{2^n}}\)
I rozumiem, że wtedy podstawiając do wzoru \(\displaystyle{ U_n-U_{n-1}=...}\) byłoby \(\displaystyle{ \frac{2T_{n-1}+2n-1}{2^n} - U_{n-1}}\)
Tylko tu z kolei nie wiem co podstawić za \(\displaystyle{ U_{n-1}}\)...
Sorry za pewnie głupie pytania i brak podstaw, ale nigdy wcześniej nie rozwiązywałem takich rekurencji...-- 29 sty 2012, o 23:40 --
Poza tym w moim pierwszym poście jest błąd:
\(\displaystyle{ T_n=2T_{n-1}+2n-1 = 2(2T_{n-2}+2(n-1)-1)+2n-1}\)
Warunki brzegowe:
\(\displaystyle{ T_0=0}\)
\(\displaystyle{ T_1=1}\)
Ktoś mógłby mi pomóc wyliczyć to? Już nawet nie musi być użyta metoda czynnika sumacyjnego, wystarczy rozwiązanie powyższego równania...
Nie do końca rozumiem dlaczego \(\displaystyle{ s_n=\frac{1}{2^{n-1}}}\) - to "n-1 do kwadratu" jest wzięte z \(\displaystyle{ a_{n-1}}\) we wzorze \(\displaystyle{ s_n=\frac{a_1a_2\ldots a_{n-1}}{b_2b_3\ldots b_n}}\) ? I dlaczego potem można to skrócić do \(\displaystyle{ s_n=\frac{1}{2^n}}\) ?
Pomnożenie rekurencji przez \(\displaystyle{ s_n}\) wyglądałoby tak?:
\(\displaystyle{ T_n * \frac{1}{2^n} = 2T_{n-1}+2n-1 * \frac{1}{2^n}}\)
I rozumiem, że wtedy podstawiając do wzoru \(\displaystyle{ U_n-U_{n-1}=...}\) byłoby \(\displaystyle{ \frac{2T_{n-1}+2n-1}{2^n} - U_{n-1}}\)
Tylko tu z kolei nie wiem co podstawić za \(\displaystyle{ U_{n-1}}\)...
Sorry za pewnie głupie pytania i brak podstaw, ale nigdy wcześniej nie rozwiązywałem takich rekurencji...-- 29 sty 2012, o 23:40 --
Jednak musi być \(\displaystyle{ s_n=\frac{1}{2^{n-1}}}\), to drugie jest błędne.Qń pisze: Widać więc, że w tym wypadku jest \(\displaystyle{ s_n=\frac{1}{2^{n-1}}}\), albo wygodniej: \(\displaystyle{ s_n=\frac{1}{2^n}}\).
Poza tym w moim pierwszym poście jest błąd:
Powinno być:\(\displaystyle{ T_n=2T_{n-1}+2n-1=2(2T_{n-2}+2_{n-1}-1)+2n-1}\)
\(\displaystyle{ T_n=2T_{n-1}+2n-1 = 2(2T_{n-2}+2(n-1)-1)+2n-1}\)
Warunki brzegowe:
\(\displaystyle{ T_0=0}\)
\(\displaystyle{ T_1=1}\)
Ktoś mógłby mi pomóc wyliczyć to? Już nawet nie musi być użyta metoda czynnika sumacyjnego, wystarczy rozwiązanie powyższego równania...