GATE CSE 2004 | Question: 84

Question

The recurrence equation
$ T(1) = 1$
$T(n) = 2T(n-1) + n, n \geq 2$

evaluates to

• A. $2^{n+1} - n - 2$
• B. $2^n - n$
• C. $2^{n+1} - 2n - 2$
• D. $2^n + n $

Comments

Initial equation should be T(0)=1 not T(1) =1.

---

what role does the condition given play that n>=2 ?

---

@Arjunsir @GO Classes does this recurrence fail the regularity condition? 

Answer 1

Here, $T(1)=1$ and

$\begin{align} T(n)&=2T(n-1)+n\\&=2^2T(n-2)+2(n-1)+n;~[\text{Putting }T(n-1)=2T(n-2)+(n-1)]\\&=2^3T(n-3)+2^2(n-2)+2(n-1)+n;~[\text{Doing so}]\\&=\cdots\\&=2^{n-1}T(n-(n-1))+2^{n-2}\{n-(n-2)\}+2^{n-3}\{n-(n-3)\}+\cdots+2(n-1)+n\\&=2^{n-1}T(1)+2^{n-2}(2)+2^{n-3}(3)+\cdots+2^{1}(n-1)+2^{0}n\end{align}$

 

Now putting $T(1)=1$ as given,

$\begin{align}\therefore T(n)&=2^{n-1}(1)+2^{n-2}(2)+2^{n-3}(3)+\cdots+2^{1}(n-1)+2^{0}n \tag{i} \\ \Rightarrow 2T(n)&=2^n(1)+2^{n-1}(2)+2^{n-2}(3)+\cdots+2^2(n-1)+2^{1}n \tag{ii}\end{align} $

 

$\mathrm{no(ii)}-\mathrm{no(i)}\Rightarrow\\ \begin{align}T(n)&=2^n+2^{n-1}(2-1)+2^{n-2}(3-2)+\cdots+2^1(n-(n-1))-2^{0}n\\&=(2^{n}+2^{n-1}+2^{n-2}+\cdots+2)-n\\&=(2+2^2+2^3+\cdots+2^{n-1}+2^n)-n; ~[\text{Rearranging}]\\&=\frac{2(2^n-1)}{2-1}-n;~[\scriptsize\because a+ar+ar^2+\cdots+ar^n=\frac{a(r^{n+1}-1)}{r-1}\text{ as Geometric Series}]\\&=2^{n+1}-2-n \end{align}$

 

$\therefore T(n)=2^{n+1}-n-2$.

 

So the correct answer is A.

Comments

in eq 1 before (3) it will be $2^{n-3}$

---

Thanks, it was a typing mistake.

---

Thank you for a detailed explanation

---

for me this is the best answer it was so clear @techbd123

---

Best Explanation

Answer 2

One simple way to answer such question is:

put n=2 ( any small case and find its value and put in all the equations )

T(1) = 1

T(2) = 4

T(3) = 11

 

option a)  4

option b) 2

option c) 2

option d) 6

 

Now when we put n=2 in the equations we get the correct answer only in option a.

If multiple eq gives the correct answer then we have to take other case and check again on the remaining equations which were giving the correct answer.

Answer 3

T(2) = 4.

Option A.

Solved under 30 seconds.