Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
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

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

share|improve this answer
    
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

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 $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.