I'm working with induction proofs involving inequalities and I am encountering example proofs that wish to show things of the sort, $n!\le\ n^n$ for every positive integer. The proof given in the inductive step is, $(n+1)!$ $=$ $(n+1)\dot\ n!$ $\le$ $(n+1)n^n$$\lt$ $(n+1)(n+1)^n$ $=$ $(n+1)^{n+1}$ I'm not quite clear why the strict inequality was admissible in the proof, if I'm trying to show $n!\le\ n^n$, rather than $n!\lt\ n^n$. Thanks for any insight.
Asked
Active
Viewed 1,001 times
3
-
What this shows is that for $n>1$ it is true that $n! < n^n$. – abnry Sep 26 '13 at 00:30
-
BTW $(n+1)(n+1)^n = (n+1)^{n+1}$ in the last part of your inductive step. – Geoff Pointer Sep 26 '13 at 00:32
-
So my text is wrong in stating that this demonstrates $n\le n^n$ for all positive integers? – Gregg R Sep 26 '13 at 00:32
-
No, your text is not wrong, if you mean that $n!\leq n^n$? See the answer by Twink below. If we know $a < b$ then $a \leq b$ is a true statement. But not the other way around. – Geoff Pointer Sep 26 '13 at 00:35
-
Then this example could have used the non-strict inequality throughout the entire inductive step? – Gregg R Sep 26 '13 at 00:37
1 Answers
3
You can change $<$ by $\leq$ but not $\leq$ by $<$.
For example, we have $1 < 2$, so $1 \leq 2$ is also true.
On the other hand, we have $1 \leq 1$, but it's not true that $1 < 1$.
Also, you proved $n! < n^n$ for $n > 1$, but this is not true for every positive integer, since for $n=1$ we get the equality. But it's true that $n! \leq n^n$ for every positive integer $n$.
Twnk
- 2,436