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.
Best Answer
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$