# Solve the recurrence $T(n) = 2T(n-1) + n$

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?

-
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

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

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

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

-
thankyou Nameless..but this is not quite the method I was looking for.. – Vishnu Vivek Nov 19 '12 at 15:55
@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$

-
could you please elaborate. – Vishnu Vivek Nov 18 '12 at 17:51
hmmm... do you know what substitution is? – Norbert 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
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 – Norbert 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.$$

-
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

Let's use the method of annihilators to turn this into a third-order, homogeneous recurrence, and then solve with a characteristic equation. First, we write the recurrence so $n$ is the least index: $$T(n) - 2T(n-1)= n \implies T(n+1)-2T(n) = n+1$$

Then, we rewrite the recurrence in terms of the shift operator $E$: $$(E-2)T(n) = n+1$$

Applying the $(E-1)$ operator to both sides of the equation, we have: $$(E-1)^2(E-2)T(n) = (E-1)^2(n+1)$$

Now, since $(E-1)^2(n+1) = 0$ (it annihilates that term), we have: $$(E-1)^2(E-2)T(n) = 0$$

The characteristic equation is, then $(r-1)^2(r-2)=0$, so our roots are $r=1$ (with multiplicity $2$) and $r=2$. So, the recurrence has the form: \begin{align*} T(n) &= c_1\cdot 2^n + c_2 \cdot n1^n + c_3 \cdot 1^n\\ &= c_1\cdot 2^n + nc_2 + c_3 \end{align*}

Using the recurrence relation, we compute $T(1) = 1, T(2) = 4, T(3) = 11$ and can now solve for $(c_1, c_2, c_3)$, which gives the solution $(2, -1, -2)$.

-