Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Solve the recurrence $T(n) = 2T(n-1) + n$ where $T(1) = 1$ and $n\ge 2$.

The final answer is $2^{n+1}-n-2$

Can anyone arrive at the solution.

share|improve this question
    
Have you considered induction? –  Nameless Nov 18 '12 at 17:45
    
Yeah but it goes a long way around. I need a simple solution. –  VISHNU VIVEK Nov 18 '12 at 17:48
    
Induction in this case is very simple. Shouldn't take more than two lines. –  Nameless Nov 18 '12 at 17:55
    
I'd love to see your answer. –  VISHNU VIVEK Nov 18 '12 at 18:01
    
If you know the solution, induction works. If you don;'t know a solution, equations like this work in the same way as linear differential equations. There is a generic solution $G(n)=2G(n-1)$ so $G(n) = 2^nG(0)$ and a special solution $S(n)=2S(n-1)+n$ - a solution of the form $S(n)=p(n)$ can be tried - generally with $p(n)$ of the same degree as the function of $n$ in the recurrence (in this case linear) - but of higher degree when the characteristic equation of the recurrence has a root (multiple root) equal to 1. Then $T(n)=S(n)+aG(n)$ with $a$ to fit initial condition. –  Mark Bennet Nov 18 '12 at 18:02

4 Answers 4

up vote 4 down vote accepted

\begin{align} T(n) & = 2 T(n-1) + n = 2(2T(n-2) + n-1) + n = 4T(n-2) + 2(n-1) + n\\ & = 8 T(n-3) + 4(n-2) + 2(n-1) + n = 2^k T(n-k) + \sum_{j=0}^{k-1} 2^j (n-j)\\ & = 2^{n-1} T(1) + \sum_{j=0}^{n-2}2^j (n-j) = 2^{n-1} + \sum_{j=0}^{n-2}2^j (n-j) \end{align} \begin{align} \sum_{j=0}^{n-2}2^j (n-j) & = n \sum_{j=0}^{n-2}2^j - \sum_{j=0}^{n-2} j2^j = n(2^{n-1}-1) - \dfrac{n \cdot 2^n - 3 \cdot 2^n + 4}2\\ & = n(2^{n-1}-1) - (n \cdot 2^{n-1} -3 \cdot 2^{n-1} + 2) = 3 \cdot 2^{n-1} -n - 2 \end{align} Hence, $$T(n) = 2^{n-1} + 3 \cdot 2^{n-1} -n - 2 = 2^{n+1} - n - 2$$

EDIT (Adding details)

First note that $\displaystyle \sum_{j=0}^{n-2}2^j$ is sum of a geometric progression and can be summed as shown below.$$\sum_{j=0}^{k} x^j = \dfrac{x^{k+1} -1}{x-1}$$ $\displaystyle \sum_{j=0}^{n-2} j2^j$ is a sum of the form $\displaystyle \sum_{j=0}^{k} jx^j$ $$\sum_{j=0}^{k} jx^j = x \sum_{j=0}^{k} jx^{j-1} = x \dfrac{d}{dx} \left( \sum_{j=0}^k x^j\right) = x \dfrac{d}{dx} \left( \dfrac{x^{k+1} - 1}{x-1}\right) = x \left( \dfrac{kx^{k+1} - (k+1) x^k +1}{(x-1)^2} \right)$$

share|improve this answer
    
Hey Marvis, your answer seems the best one. (1) But how did you expand the summation in the fourth line. Is there any formula? (2) And in the last step, why did you add 2^(n-1). Where did it come from? –  VISHNU VIVEK Nov 19 '12 at 16:21
    
@VISHNUVIVEK (1) I have added the details for the summations. (2) If you look at the third line you have $$T(n) = 2^{n-1} + \sum_{j=0}^{n-2}2^j (n-j)$$ Hence, there is a $2^{n-1}$ term in $T(n)$. –  user17762 Nov 19 '12 at 20:57
    
Technically speaking, this is not a proof. The problem lies in the lack of justification of the fifth equal sign (the one just before $2^kT(n-k)+\cdots$). –  Did Nov 19 '12 at 22:03
    
@did True. At some stage induction has to be used. But I guess that is not what exactly OP is interested in. The OP wants in some sense a universal trick to solve these recurrence equations. –  user17762 Nov 19 '12 at 22:20

Induction: For $n=1$, $T(1)=1=2^{1+1}-1-2$. Suppose $T(n-1)=2^n-n+1-2=2^n-n-1$. Then $T(n)=2T(n-1)+n=2^{n+1}-2n-2+n=2^{n+1}-n-2$ which completes the proof.

share|improve this answer
    
thankyou Nameless..but this is not quite the method I was looking for.. –  VISHNU VIVEK Nov 19 '12 at 15:55
1  
@VISHNUVIVEK but this is not quite the method I was looking for... Are we supposed to guess the method you were looking for? –  Did Nov 19 '12 at 22:01

Hint: substitute $T(n)=G(n)-n-2$

share|improve this answer
    
could you please elaborate. –  VISHNU VIVEK Nov 18 '12 at 17:51
    
hmmm... do you know what substitution is? –  userNaN Nov 18 '12 at 17:53
    
Have you actually tried what is suggested? –  Mark Bennet Nov 18 '12 at 17:55
    
It makes sense, but the answer won't be given during exam. So, I don't think it's a good idea to go from the answer. –  VISHNU VIVEK Nov 18 '12 at 18:08
1  
Then you should take into account comment of Mark Bennet given to your question. It shows the main idea. In fact you haven't mentioned that you need general method for solving such questions at exams, you just asked the way to solve this recurrence –  userNaN Nov 18 '12 at 18:10

This recurrence $$T(n) = 2T(n-1) + n$$ is difficult because it contains $n$. Let $D(n) = T(n) - T(n-1)$ and compute $D(n+1) = 2D(n) + 1$ this recurrence is not so difficult. Of course $D(1) = 4 - 1 = 2 + 1$.

The sequence $D(n)$ goes: $2 + 1$, $2^2 + 2 + 1$, $2^3 + 2^2 + 2 + 1$. $D(n) = 2^{n+1}-1$.

Now $$T(n) = \sum_{i=1}^n D(i) = 2 \sum_{i=1}^n 2^{i} - \sum_{i=1}^n 1 = 2^{n+1}-2-n.$$

share|improve this answer
    
Hey Sperners, you've assumed D(n)=T(n)−T(n−1). Can you tell me a reason why you've assumed like that. –  VISHNU VIVEK Nov 19 '12 at 16:55
    
@VISHNUVIVEK, I define $D$ this way to get a recurrence without $n$ in it. –  sperners lemma Nov 19 '12 at 17:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.