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

I have trouble solving following recurrence.

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

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

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

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