Solving a recurrence relation using back substitution.

This is related to analysis of algorithms (divide and conquer), but since it's mostly math, I thought it would be better to post here instead. I'm trying to solve a recurrence relation using back substitution. $n = 2^k, k \ge 1$

The relationship is given by: $$n >2,\;w(n)=2w(\frac n2) + 4$$ And when $n=2, \; w(n)=1$

The procedure I have followed so far is this:

Substituting $t = 2^k, \; k \ge 1$ into the relation:

Line 1: \begin{align} w(t) & = 2w(\frac t2) + 4 \\ & = 2w(\frac {2^k}2) + 4 \\ & = 2w(2^{k-1}) + 4 \end{align}

Then I started doing the back substitution by taking the value of $w(t)$ into itself:

Line 2: \begin{align} w(t) & = 2 \Big ( 2w(\frac {2^{k-1}}2)+4 \Big ) + 4 \\ & = 2^2w (2^{k-2}) + 8 + 4 \\ \end{align}

Line 3: \begin{align} w(t) & = 2^2 \Big ( 2w(\frac {2^{k-2}}2)+4 \Big ) + 8 + 4 \\ & = 2^3w (2^{k-3}) + 16 + 8 + 4 \\ & = 2^3w (2^{k-3}) + 2^4 + 2^3 + 2^2 \\ \end{align}

With that, I felt confident that I could figure out the general relation for line $i$.

$$line \,i = 2^i w(2^{k-i}) + 2^{i+1} + 2^i + 2^{i-1} ... + 4$$

But then it's where it got weird. I evaluated for the base case: $2^{k-i}=2, \; i=k-1$ So basically, I made it fall into the base case.

\begin{align} line \,k & = 2^{k-1} w(2^{k-(k-1)}) + 2^{k-1+1} + 2^{k-1} + 2^{k-2}... + 4 \\ & = 2^{k-1} w(2) + 2^{k} + 2^{k-1} + 2^{k-2} ... + 4 \\ & = 2^{k-1} (1) + 2^{k} + 2^{k-1} + 2^{k-2} ... + 4 \\ & = 2^{k-1} - 2^2\sum_{j=0}^{k-2} {2^j} \\ & = 2^{k-1} - 2^2 \, 2^{k-2+1} - 1 \\ & = 2^{k-1} - 2^2 \, 2^{k-1} - 1 \\ \end{align}

What is it that I'm doing something wrong up to this point? In the end, I got something that I couldn't verify by induction, so I'm fairly certain the mistake was in the steps above.

Apologies for the messy use of LaTeX, it's my first time.

First, a plus instead of a minus, $2^{k-1}(1) + 2^k + 2^{k-1} + \dots + 4 = 2^{k-1} + 2^2\sum_{j=0}^{k-1}2^j$
Second, you need to factor in the $2^2$
$2^{k-1} + 2^2\sum_{j=0}^{k-1}2^j = 2^{k-1} + 2^2(2^{k-2+1}-1) = 2^{k-1} +2^{k+1} - 4 = \frac{t}{2} + 2t - 4 = \frac{5t}{2} - 4$
• Thank you! My only concern is regarding $\sum_{j=0}^{k-1}$, shouldn't it be $\sum_{j=0}^{k-2}$, since factoring $2^2$ back in would lead to the original last term $2^k$? – Emyr Oct 23 '12 at 14:05