Funkcja kosztu algorytmu

[lunex]

Treść zadania:
Niech funkcja kosztu pewnego algorytmu ma postać \(\displaystyle{ T(n) = 4\cdot T(n-1) +1, T(0 ) = 1}\). Oszacuj, koszt tego algorytmu, odpowiedź uzasadnij.

No i mam problem z wyznaczeniem wzoru ogólnego, robię tak:
\(\displaystyle{ T(0)=1+0}\)
\(\displaystyle{ T(1)=4+1}\)
\(\displaystyle{ T(2)=16+5}\)
\(\displaystyle{ T(3)=64+21}\)
\(\displaystyle{ T(4)=256+85}\)
czyli \(\displaystyle{ T(n)=4^n +}\) [i tutaj jest problem ;p]

Bardzo proszę o pomoc.

[Konikov]

Mi zazwyczaj wyznaczanie pierwszych wyrazów mało dawało, robiłem tak dopóki nie znałem lepszych narzędzi ;] Można oczywiście zgadnąć i udowodnić indukcyjnie, ale tutaj robi się to tak:

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

Zauważamy, że mamy za każdym razem coraz większą potęgę 4, a wyrazy wolne to \(\displaystyle{ 4^0, 4^1, 4^2...}\)

Więc:
\(\displaystyle{ T(n) = 4^n + \sum_{i=1}^{n} 4^i}\)

Pozdrawiam ;]

---Edit---
Postawię piwo temu, kto napisze zwarty wzór na \(\displaystyle{ \sum_{i=1}^{n} 4^i}\) ;]

[paladin]

Mam nadzieję, że to żart Ale jakby nie był, poszukaj pod "suma ciągu geometrycznego".

[Konikov]

Joykiller ;P