Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The question:

Use resubstitution to solve the following recurrence equation:

$$T(n) = 2T(n-1) + n;\; n \ge2\text{ and }T(1) = 1.$$

So far I have this:

$$\begin{align}T(n) &= 2T(n-1) + n\\ &= 2(2T(n-2) + (n-1)) + n\\ &= 4T(n-2) + 3n -2\\ &= 2(4T(n-3) + 3(n-1) -2) + n\\ &= 2(4T(n-3) + 3n -3 -2) + n\\ &= 2(4T(n-3) + 3n -5) + n\\ &= 8T(n-3) + 6n - 10 + n\\ &= 8T(n-3) +7n -10\end{align}$$

I'm just wondering if so far, the way I'm approaching this is correct. Any help is appreciated, thank you.

share|cite|improve this question
Why don't you try to see a trend and prove it's correct? (A trend would be a function for $T(n)$ in terms of $T(0)$ or $T(1)$.) – andybenji Dec 10 '12 at 2:26
up vote 1 down vote accepted

You are perhaps making it a little harder than necessary to take the next step. When you unwrap a recurrence in this way, it’s often a good idea not to combine the terms that don’t involve $T$:

$$\begin{align*} T(n)&=2T(n-1)+n\\ &=2\Big(2T(n-2)+(n-1)\Big)+n\\ &=2^2T(n-2)+2(n-1)+n\\ &=2^2\Big(2T(n-3)+(n-2)\Big)+2(n-1)+n\\ &=2^3T(n-3)+2^2(n-2)+2(n-1)+n\;. \end{align*}$$

When you leave the intermediate results in this form, it’s very easy to see that after $k$ steps you’ll have

$$\begin{align*} T(n)&=2^kT(n-k)+2^{k-1}\big(n-(k-1)\big)+2^{k-2}\big(n-(k-2)\big)+\ldots+2^1(n-1)+2^0n\\ &=2^kT(n-k)+\sum_{i=0}^{k-1}2^i(n-i)\;. \end{align*}$$

This makes it easy to see what the final step of the unwrapping will yield, and it also tells you that you’ll need to be able to work out


for some value of $m$. One of those last two sums is easy, since it’s geometric; the other is a little trickier, but it’s been discussed many times on this site.

share|cite|improve this answer

Your Answer


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.