Rozwiązanie rekurencji metodą czynnika sumacyjnego

[el ZAX]

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...

[Qń]

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.

[el ZAX]

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 --

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}}\).

Jednak musi być \(\displaystyle{ s_n=\frac{1}{2^{n-1}}}\), to drugie jest błędne.


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}\)

Powinno być:
\(\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...