3
$\begingroup$

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.

  • 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)$.)2012-12-10

1 Answers 1

1

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.