# proof by induction help

• Jan 24th 2011, 11:43 PM
yaykittyeee
proof by induction help
I've been reviewing mathematical induction and I don't really get how to prove inequalities by induction. I've been working on this problem for a while..

$\displaystyle 2^n\leq(n+1)!$

so far I've proved n=1 for the base, then I assume n=k.
$\displaystyle 2^k\leq(k+1)!$

then, I use n=(k+1)..
$\displaystyle 2^(k+1)\leq((k+1)+1)!$

this is where i get confused, I did this..
$\displaystyle 2\bullet(k+1)!=((k+1)+1)!$
I multiplied by 2 because you can rewrite $\displaystyle 2^(k+1)$ as $\displaystyle 2^k\bullet2$ but i'm not sure if multiplying by two on the other side is right since it's an inequality and not an equation like what i've been working with up until now. I would really appreciate help with trying to solve this
• Jan 25th 2011, 12:16 AM
Prove It
There's actually no need for induction...

$\displaystyle \displaystyle 2^n = 2\cdot 2 \cdot 2 \cdot \dots \cdot 2$ ($\displaystyle \displaystyle n$ times)

$\displaystyle \displaystyle (n+1)! = (n+1)\cdot n \cdot (n - 1) \cdot \dots \cdot 3 \cdot 2$ (again, $\displaystyle \displaystyle n$ terms).

Since each has $\displaystyle \displaystyle n$ terms and each term in $\displaystyle \displaystyle n!$ is no less than $\displaystyle \displaystyle 2$, that means

$\displaystyle \displaystyle 2 \cdot 2 \cdot 2 \cdot \dots \cdot 2 < (n + 1) \cdot n \cdot (n - 1) \cdot \dots \cdot 3 \cdot 2$

$\displaystyle \displaystyle 2^n < (n+1)!$ for $\displaystyle \displaystyle n > 1$ (if $\displaystyle \displaystyle n = 1$ then $\displaystyle \displaystyle 2^n = n!$).
• Jan 25th 2011, 12:34 AM
yaykittyeee
the question asks to prove in by mathematical induction, but thanks for the help.
i don't know how i ended up with two threads. sorry, i didn't mean to post this one, i think i was trying to preview it.
• Jan 25th 2011, 12:53 AM
tonio
Quote:

Originally Posted by yaykittyeee
I've been reviewing mathematical induction and I don't really get how to prove inequalities by induction. I've been working on this problem for a while..

$\displaystyle 2^n\leq(n+1)!$

so far I've proved n=1 for the base, then I assume n=k.
$\displaystyle 2^k\leq(k+1)!$

then, I use n=(k+1)..
$\displaystyle 2^(k+1)\leq((k+1)+1)!$

this is where i get confused, I did this..
$\displaystyle 2\bullet(k+1)!=((k+1)+1)!$
I multiplied by 2 because you can rewrite $\displaystyle 2^(k+1)$ as $\displaystyle 2^k\bullet2$ but i'm not sure if multiplying by two on the other side is right since it's an inequality and not an equation like what i've been working with up until now. I would really appreciate help with trying to solve this

Well,

$\displaystyle 2^{k+1}=2^k\cdot 2<(k+1)!\cdot 2 \,\,(Ind.\,\, hypothesis) <(k+1)!(k+2) \,\,(since \,\,2 < k+2)=(k+2)!$ . Q.E. D.

Tonio