GATE Overflow Test Series | Mixed Subjects | Test 1 | Question: 11

Question

What is the solution to the following recurrence relation?

• $T(n) = 3T(n-1) + 1$
• $T(1) = 1$

• A. $3^{n}$
• B. $3^{n-1}$
• C. $3^{n}-1$
• D. $\frac{3^{n}-1}{2}$

Answer 1

• $T(n) = 3T(n-1) + 1 \quad \rightarrow (1)$
• $T(1) = 1$

From the equation $(1),$ we get

• $T(n-1) = 3T(n-2) + 1$ 
• $T(n-2) = 3T(n-3) + 1$ 
• $T(n-3) = 3T(n-4) + 1$ 
• $T(n-4) = 3T(n-5) + 1$ 
• $\vdots\;\;\;\;\;\vdots$

Put these values, in the equation $(1),$ we get

• $T(n) = 3T(n-1) + 1$
• $T(n) = 3[3T(n-2) + 1] + 1$
• $T(n) = 3^{2}T(n-2) + 3 + 1$
• $T(n) = 3^{2}[3T(n-3) + 1] + 3 + 1$
• $T(n) = 3^{3}T(n-3) + 3^{2} + 3 + 1$
• $T(n) = 3^{3}[3T(n-4) + 1] + 3^{2} + 3 + 1$
• $T(n) = 3^{4}T(n-4) + 3^{3} + 3^{2} + 3 + 1$
• $T(n) = 3^{4}[3T(n-5) + 1] + 3^{3} + 3^{2} + 3 + 1$
• $T(n) = 3^{5}T(n-5) +3^{4} + 3^{3} + 3^{2} + 3 + 1$
• $\vdots\;\;\;\;\;\vdots$

$i^{\text{th}}$ term, we get

$T(n) = 3^{i}T(n-i) +3^{i-1} + 3^{i-2} + 3^{i-3} + \dots + 3^{3} + 3^{2} + 3^{1} + 3^{0}$

Given that$:T(1) = 1$

Put $n-i = 1 \implies i = n - 1$

Now, $T(n) = 3^{n-1}T(1) +3^{n-2} + 3^{n-3} + 3^{n-4} + \dots + 3^{3} + 3^{2} + 3^{1} + 3^{0}$

$\implies T(n) = 3^{n-1}+3^{n-2} + 3^{n-3} + 3^{n-4} + \dots + 3^{3} + 3^{2} + 3^{1} + 3^{0}$

$\implies T(n) = \underbrace{3^{0} + 3^{1}  +3^{3} + 3^{4} + \dots + 3^{n-3} + 3^{n-2} + 3^{n-1}}_{\text{Total terms} = n}$

It is a GP series, with $a = 3^{0} = 1, r = 3$

Sum of GP series $S_{n} = \dfrac{a(r^{n} -1)}{r-1};\; r \neq 1$

Now, $T(n) = \dfrac{1(3^{n}-1)}{3-1} = \dfrac{3^{n} - 1}{2}.$

So, the correct answer is $(D).$

Answer 2

• $T(1) = 1$
• $T(2) = 3.T(1) + 1 = 4$
• $T(3) = 3.T(2) + 1 = 13$
• $T(4) = 3.T(3) + 1 = 40$
• $T(5) = 3.T(4) + 1 = 121$

We can see that, $T(n) = \dfrac{3^n-1}{2}$

So, the correct answer is $(D).$