# Solve the recurrence of $T(n)= 3T(n-1)+1$ with $T(0)=2$ by iteration of the recurrence

Solve the recurrence of $T(n)= 3T(n-1)+1$ with $T(0)=2$ by iteration of the recurrence. (I was told that there is no need to prove it by induction)

I googled "iteration of the recurrence." I did not really get much except general proofs. Does anyone have a good explanation of this phrase that I can use to get me started?

$$T(n) = 3T(n-1)+1 = 9T(n-2) + 3 + 1 = 27T(n-3) + 9 + 3 + 1 = ...$$ So, $$T(n) = \sum_{m=0}^{n-1} 3^m + 2\cdot3^n = \frac{5\cdot 3^n-1}{2}$$ Using the formula for a sum of a geometric series.

This cached copy tells me that 'iteration of recurrence' is a brute force way of listing the values of $T(n)$ for various values of $n$.

For example,

$T(1) = 3T(0) + 1 = 3 \cdot 2 + 1 = 7$. $T(2) = 3T(1) + 1 = 3 \cdot 7 + 1 = 3(3 \cdot 2 + 1) + 1 = 9 \cdot 2 + 3 + 1 = 22$. $T(3) = 3T(2) + 1 = 3 \cdot 22 + 1 = 3(3(3 \cdot 2 + 1)+1)+1 = 27 \cdot 2 + 9 + 3 + 1 = 67$.

We observe the pattern and guess
$T(n) = 2 \cdot 3^n + 3^{n-1} + \cdots + 1$.

• Are you using $.$ instead of "\cdot" $\cdot$ on purpose? – nbubis Jul 13 '13 at 2:30
• I am using \cdots and not the period. – Isomorphism Jul 13 '13 at 2:51
• ok.. so why not \cdot? – nbubis Jul 13 '13 at 4:20
• @Isomorphism maybe it's my browser, but I also see period there, not \cdots. Who does use \cdots for multiplication anyway? – Kaster Jul 14 '13 at 23:07
• @Kaster: Thanks for the clarification. nbubis was talking about the dot used for multiplication. Yes, I have used the '.' for multiplication. Is it confusing? – Isomorphism Jul 15 '13 at 15:25