# Thread: proof by induction help

1. ## 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\ast(k+1)!=((k+1)+1)!$
I multiplied by 2 because you can rewrite $\displaystyle 2^{k+1}$ as $\displaystyle 2^k\ast2$ 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

2. You can multiply both sides of an equation or an inequality by the same number, but your last equality is still wrong. However, it leads to the right idea.

We know (by assumption) that $\displaystyle 2^k <= (k + 1)!$. How does one obtain $\displaystyle 2^{k+1}$ from $\displaystyle 2^k$ and (n + 2)! from (n + 1)! ? $\displaystyle 2^{k+1}$ is obtained by multiplying $\displaystyle 2^k$ by 2, so let's multiply both sides of $\displaystyle 2^k <= (k + 1)!$ by 2. Then how does 2(k + 1)! compare with (k + 2)! ?

3. ok, so instead of the last equation, i did this
$\displaystyle 2(k+1)!\leq(k+2)!$
and i expanded the factorial things, but i'm not sure if this is the right way to do it.
$\displaystyle 2((k+1)(k))\leq(k+2)(k+1)(k)$
then i divided by (k+1)(k) on both sides and got
2<=(k+2)
which seems like it would prove the inequality since you can't add k to 2 and get less than 2. Is this right?

4. Basically, yes. In going from $\displaystyle 2(k+1)!\leq(k+2)!$ to $\displaystyle 2((k+1)(k))\leq(k+2)(k+1)(k)$ you not only expanded the factorials but also divided both sides of the first inequality by (k - 1)! since 2(k + 1)! = 2(k + 1)k(k - 1)!, not just 2(k + 1)k. You could divide both sides of the first inequality by (k + 1)! to get 2 <= k + 2.

Also, it is important to watch the direction of the proof. Usually a finished proof is presented as a sequence of statements, each of which implies the following. However, in constructing a proof and especially in solving an equation or an inequality we tend to go the opposite way: start from what we need to prove and simplify it until we get to something clearly true. Strictly speaking, in the end we must reverse the direction.

So here is how I would write the inductive step. Assume the induction hypothesis (IH), i.e., $\displaystyle 2^k\le (k+1)!$ for some $\displaystyle k\ge 0$. We need to prove that $\displaystyle 2^{k+1}\le(k+2)!$.

Multiplying both sides of the the IH by 2, we get

$\displaystyle 2^{k+1}\le2(k+1)!$ (*)

Also, $\displaystyle 0\le k\Rightarrow 2\le k+2\Rightarrow 2(k+1)!\le(k+2)(k+1)!=(k+2)!$. Combining this with (*), we get $\displaystyle 2^{k+1}\le(k+2)!$.

5. 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\ast(k+1)!=((k+1)+1)!$
I multiplied by 2 because you can rewrite $\displaystyle 2^{k+1}$ as $\displaystyle 2^k\ast2$ 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
Alternatively,

"If" $\displaystyle 2^k\le(k+1)!\Rightarrow\ (2)2^k\le(2)(k+1)!<(k+2)(k+1)!$

for $\displaystyle k\ge\ 1$

and since $\displaystyle (k+2)(k+1)!=(k+2)!=[(k+1)+1]!$

$\displaystyle 2^{k+1}\le(k+2)!$ "if" $\displaystyle 2^k\le(k+1)!$