6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Welcome to math Irwin :-) $\endgroup$
    – Aryabhata
    Nov 10, 2010 at 17:18
  • $\begingroup$ 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$. $\endgroup$
    – T..
    Nov 10, 2010 at 17:37
  • $\begingroup$ Hey @Moron! Thanks for the redirect $\endgroup$
    – Irwin
    Nov 10, 2010 at 18:09

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Nov 10, 2010 at 17:44
  • $\begingroup$ I updated my answer a bit. I think its better than what I had before. $\endgroup$ Nov 10, 2010 at 20:02
  • $\begingroup$ 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. $\endgroup$ Nov 10, 2010 at 23:26
3
$\begingroup$

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 $

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ That's where I'm having difficulty, showing that its true for the inductive step. $\endgroup$
    – Irwin
    Nov 10, 2010 at 17:15
  • $\begingroup$ Maybe it is because I got the formula wrong. It is now fixed. $\endgroup$ Nov 10, 2010 at 17:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .