# 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.

-
Welcome to math Irwin :-) – Aryabhata Nov 10 '10 at 17:18
It is easier to analyze (T+2) instead of T. The answer will depend on whether (n/2) is meant to be rational or integer valued (denoted by [n/2] or Floor[n/2] or $\lfloor n/2 \rfloor$. – T.. Nov 10 '10 at 17:37
Hey @Moron! Thanks for the redirect – Irwin Nov 10 '10 at 18:09

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.

-
Note that T(k) is only defined for k a power of 2. So assume T(k)=4k-2, then T(2k)=2T(2k/2)+2=2(4k-2)+2=8k-2=4(2k)-2 – Ross Millikan Nov 10 '10 at 17:44
I updated my answer a bit. I think its better than what I had before. – Vincent Ramdhanie Nov 10 '10 at 20:02
But you don't have T(k+1) defined in terms of T(k), just T(2k) in terms of T(k). Although you can extend T to all naturals>=1, the problems only tells you what it is for 2^n. – Ross Millikan Nov 10 '10 at 23:26

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$

-

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)$.

-
That's where I'm having difficulty, showing that its true for the inductive step. – Irwin Nov 10 '10 at 17:15
Maybe it is because I got the formula wrong. It is now fixed. – Ross Millikan Nov 10 '10 at 17:33