<s>[INST] 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.
 [/INST] Here is how I attempt this from the point you left off:
We know that $\rm T(1) = 2$. We are trying to prove that $\rm T(n) = 4n-2$.
This is trivially true for $n = 1$:
$ \rm \begin{eqnarray*}
    T(1) &=& 4(1) - 2\\
        &=& 4 - 2\\
        &=& 2 \\
\end{eqnarray*}
$
Assume
$\rm T(k) = 4k - 2 $
From the original definition:
$\rm T(k+1) = 2T( [k+1] / 2 ) + 2 $
//since we assumed up to $T(k)$ is correct and $(k+1)/2$ is less than $T(k)$, we substitute:
So, We have 
$ \rm \begin{eqnarray*}
    &2&( 4( (k+1) /2) - 2  ) + 2 \\
    &=& 4(k+1)- 4 + 2\\
    &=& 4(k+1) - 2
\end{eqnarray*}
$
Proven.
</s>