# Mathematical Induction

• Dec 13th 2010, 07:59 PM
Cthul
Mathematical Induction
My friend needs help and requires this work to be done by today. I hope it won't trouble anyone to elaborate how to do so.
EDIT: Where it says $\displaystyle 2^{2}$, it's supposed to be $\displaystyle 2^{N}$ I apologies.
• Dec 13th 2010, 08:02 PM
snowtea
The induction hypothesis is
$\displaystyle k < 2^k$

You assume that you have already proved this for k. Now you use this to prove $\displaystyle k+1 < 2^{k+1}$

So $\displaystyle k+1 < 2^{k} + 1$ just adds 1 to both sides of the induction hypothesis.
• Dec 13th 2010, 08:11 PM
Cthul
Quote:

Originally Posted by friend
then they change $\displaystyle 2^{k+1}$ into $\displaystyle 2^{k}+2^{k}$ because $\displaystyle 1<2^k$
and set that to $\displaystyle 2\times2^k=2^{k+1}$

He still doesn't get it.
• Dec 13th 2010, 09:00 PM
dwsmith
$\displaystyle \displaystyle k<2^k \ \mbox{multiple by 2}\Rightarrow \ 2k<2*2^k\Rightarrow k+k<2^{k+1}$

Since $\displaystyle \displaystyle k\geq n\geq 1$, we can take the 2nd k and set it equal to 1 without loss of generality.

$\displaystyle \displaystyle k+1<2^{k+1}$
• Dec 14th 2010, 02:42 AM
Quote:

Originally Posted by Cthul
My friend needs help and requires this work to be done by today. I hope it won't trouble anyone to elaborate how to do so.
EDIT: Where it says $\displaystyle 2^{2}$, it's supposed to be $\displaystyle 2^{N}$ I apologies.

P(k)

$\displaystyle k<2^k$

P(k+1)

Replace k with k+1

$\displaystyle k+1<2^{k+1}\;\;\;?$

Proof

$\displaystyle k<2^k\Rightarrow\ 2(k)<2\left(2^k\right)$

$\displaystyle 2k<2^{k+1}$

$\displaystyle 2k=k+k\Rightarrow\ (k+k)<2^{k+1}$

Since it is proven for the base case k=0 or k=1,

then $\displaystyle (k+1)<(k+k)$ for $\displaystyle k>1$

Therefore, if $\displaystyle k<2^k$

then $\displaystyle (k+1)<2^{k+1}$ since $\displaystyle (k+1)<(k+k)$ for $\displaystyle k>1$