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.

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|improve this question
1  
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
add comment

1 Answer 1

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

$$\sum_{i=0}^m2^i(n-i)=\sum_{i=0}^m2^in-\sum_{i=0}^m2^ii=n\sum_{i=0}^m2^i-\sum_{i=0}^mi2^i$$

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|improve this answer
add comment

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.