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.
 A: 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 $
A: 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.
A: If you calculate $T(n)$ you can observe that $T(n)=4n-2$.  To prove that by induction, observe that it is true for $n=1$ as $T(1)=2=4*1-2$.  Then assume it is true for $T(n)$ and prove that it is true for $T(2n)$.
