Prove by induction $T(n) = 2T(\frac{n}{2}) + 2$ 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.

HINT $\: $ From the first few values we guess $\rm\ T(2^n)\ =\ 2^{n+2}-2\ $ and induction confirms it:  
$$\rm T(2^{n+1})\ =\ 2\ T(2^n) + 2 \ =\ 2\ (2^{n+2}-2) +\ 2\ =\ 2^{n+3} - 2$$
One can extend $\rm\:T\:$ to $\:\mathbb N\:$ by defining $\rm\ T(2k+1) = 2\ T(k+1)-2 $ and now one easily proves by induction that $\rm\ T(k) = 4\:k-2\ $ since
$\rm\quad\quad\quad\quad\quad\quad\quad T(2k+1)\ =\ 2\ T(k+1)-2\ =\ 2\ (4k+2)-2\ =\ 4(2k+1)-2 $
$\rm\quad\quad\quad\quad\quad\quad\quad\quad\quad\ T(2k)\ =\ 2\ \ \ \ T(k)\ \ +\ \ \: 2\ =\ 2\ (4k-2) + 2\ =\ 4 (2k) - 2 $
