I'm stuck with this induction proof:
So far, given:
$\begin{align*} T(1) & = 2 \\ T(n) & = 2T(n/2)+2 \\ & = 2(2T(n/[2^2])+2) + 2 \\ & = [2^2]T(n/[2^2]) + [2^2] + 2 \\ & = [2^2](2T(n/[2^2])+2) + [2^2] + 2 \\ & = [2^3]T(n/[2^3]) + [2^3] + [2^2] + 2 \\ & = [2^3]T(n/[2^3]) + 2\{[2^2] + [2^1] + 1\} \\ & \vdots \\ & = [2^k]T(n/[2^k]) + 2\{2^{k} - 1\} \end{align*}$
How then do I show this to be correct (the proof). So far I have:
Let $(n/[2^k]) = 1$
$\Rightarrow n = 2^k$
So, $T(n) = nT(1) + 2(n - 1)$
$T(n) = 4n - 2$ //This is where I'm stuck.
Proof (by induction):
When $n = 1$, $T(1) = 2$.
Assume $T(k)$ is true [$T(n) = 4n - 2$] //This is where I am stuck.