1
$\begingroup$

I have trouble solving following recurrence.

$$T(n)=T(n-1)+3^{n-1}$$

So far I tried annihilators but it doesn't work.

$\endgroup$
  • 1
    $\begingroup$ hint: sum these equations from n=1 to n=k $\endgroup$ – Tī-Kong n̂g Dec 14 '13 at 23:19
  • $\begingroup$ Here is a technique. $\endgroup$ – Mhenni Benghorbal Dec 15 '13 at 3:48
1
$\begingroup$

That's just $T(n) = C+\sum_{k=?}^n 3^{k-1}$, where the lower limit and the constant depend on base cases that you haven't given in the question.

The sum of powers of $3$ is a finite geometric series which has standard closed-form formulas.

$\endgroup$
0
$\begingroup$

Another way (out of many). Denote $a_n=\frac{T_n}{3^{n-1}}$ to get $$ a_n=\frac{1}{3} a_{n-1}+1=\frac{1}{3^2}a_{n-2}+\frac{1}{3}+1=\ldots \frac{1}{3^{n-1}}a_1+\sum_{k=0}^{n-2}\frac{1}{3^k} $$ Hence $$ T_n=T_1+3^n \cdot \frac{1-\frac{1}{3^{n-1}}}{1-\frac{1}{3}} $$ Can you handle from here (note you didn't provide boundary value).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.