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

Question

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?

Nathaniel Bubis · Answer 1 · 2013-07-13T02:43:43.763

4

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

edited Jul 13 '13 at 02:43

answered Jul 13 '13 at 02:22

Nathaniel Bubis

33,018

score 4 · Answer 2 · edited Jan 29 '15 at 22:17

4

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

edited Jan 29 '15 at 22:17

Khosrotash

24,922

answered Jul 13 '13 at 02:27

Isomorphism

5,693

Are you using $.$ instead of "\cdot" $\cdot$ on purpose? – Nathaniel Bubis Jul 13 '13 at 02:30
I am using \cdots and not the period. – Isomorphism Jul 13 '13 at 02:51
ok.. so why not \cdot? – Nathaniel Bubis Jul 13 '13 at 04: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
@Isomorphism well, in some (many? most?) countries period is used to separate integer and decimal parts of the number. – Kaster Jul 15 '13 at 18:02

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

2 Answers2