# Solve the recurrence T(n) = 3T(n-1)+1 with T(0) = 4 using the iteration method. Simplify algebraically. Please show me your all work.

### 2 Answers | Add Yours

Notice that the problem provides an equation that relates two consecutive terms and `T(0) = 4` , hence, considering n = 1 yields:

`T(1) = 3T(1-1)+1 => T(1) = 3T(0)+1`

Substituting 4 for T(0) yields:

`T(1) = 3*4+1 => T(1) = 13`

`T(2) = 3T(2-1)+1 => T(2) = 3*T(1) + 1 => T(2) = 3*13 + 1 => T(2) = 40`

**Hence, since the problem provides T(0) = 4 and the equation that relates two consecutive terms, you may find any term but only knowing the previous term.**

Tn = 3Tn-1 +1 by data.

We use this relation for n = 1, 2, 3 etc and generalise for n = n.

Therefore for n = 1,T1 = 3T0 +1

For n=2, T2 = 3T1+1 = 3(3T0+1)+1 = 3^2T0+3+1

For n = 3, T3 = 3T2+1 = 3(3^2T0+3+1) +1 = 3^3T0+3^2+2+1

Similarly for n = 4, T4 = 3^4T0+3^3+3^2+3+1 = 3^4T0+(3^4-1)/(3-1), as a^n +a^n-1 +a^n-2 +...+a^2 +a +1 = (a^n - 1)(a-1)

Similarly for n = n, Tn = 3^nT0+ (3^n-1)/(3-1)

But T0 = 4 by data.

Tn = 3^n *4 +(3^n -1)/2

Tn = 3^n {4+1/2} - 1/2

Tn = {3^n*9 -1}/2

Tn = {3^(n+2) -1}/2.

You can easily verify. For n = 0, T0 = {3^(0+2) -1}/2 = 4,

For n =1, T1 = {3^(1+2) - 1}/2 = 13

For n = 2, T3 = {3^(2+2) -1}/2 = 40.

**So Tn = {3^(n+2) -1}/2.**