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.
