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.

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.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

A pair of mistakes, all in the last few equalities.

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$

share|improve this answer
    
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
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.