Równanie rekurencyjne

[sandra-91]

\(\displaystyle{ T(n)=\begin{cases} 1, \ n=1\\2T(n-1)+1, \ n \ge 2 \end{cases}}\)

\(\displaystyle{ n=2^k}\)

Rozwiązałam:
\(\displaystyle{ T(2^k)=2T(2^k-1)+1=}\)

\(\displaystyle{ = 2(2T(2^k-2)+1)+1=}\)

\(\displaystyle{ =2(2(2T(2^k-3)+1)+1)+1=}\)

\(\displaystyle{ =2^3T(2^k-3)+4+2+1=}\)

\(\displaystyle{ =2^kT(2^k-k)+2^{k-1}+2^{k-2}+...+2+1=}\)

No i utknęłam, nie wiem, co zrobić z \(\displaystyle{ T(2^k-k)}\)

[yorgin]

A dlaczego zaczynasz od \(\displaystyle{ T(2^k)}\), a nie po prostu od \(\displaystyle{ T(k)}\)? Życie się uprości, bo dojdziesz do \(\displaystyle{ T(1)}\) po \(\displaystyle{ (k-1)}\) krokach.

[sandra-91]

Rzeczywiście, jeśli zaczniemy od T(k), to jest łatwiej obliczyć. Spróbowałam i mi wyszło:

\(\displaystyle{ =k \cdot T(k-k)+(k-1)+(k-2)+...+2+1=}\)

No i mamy \(\displaystyle{ T(k-k)=T(0)}\) Nic z tym nie możemy zrobić. Skoro mamy w równaniu \(\displaystyle{ T(1)=1}\).

[yorgin]

Ponieważ wykonałaś \(\displaystyle{ k}\) kroków, a powinnaś zatrzymać się na \(\displaystyle{ (k-1)}\) krokach. Lub ewentualnie przyjąć, że \(\displaystyle{ T(l)=0, l<1}\) (co czasem się robi).