# False statement proven by induction?: $n\geq a\Rightarrow n!\geq a^n, n\in \mathbb{N}-\left \{ 0 \right \}$

Can you spot my mistake? I will show the false statement, that $n\geq a\Rightarrow n!\geq a^n, n\in \mathbb{N}-\left \{ 0 \right \}$, with induction

For $n=1$ , $1\geq a\Rightarrow 1!\geq a^1\Rightarrow 1 \geq a$ which is true.

Suppose that $n\geq a\Rightarrow n!\geq a^n, n\in \mathbb{N}-\left \{ 0 \right \}$

Then, $n\geq a\Rightarrow (n+1)!\geq nn!\geq aa^n=a^{n+1}$ which yields that $n+1\geq a\Rightarrow(n+1)!\geq a^{n+1}$.

Therefore, $n\geq a\Rightarrow n!\geq a^n$ But for $n=3,a=2$ using the inequality we just proved $3\geq 2\Rightarrow3!\geq 2^3\Leftrightarrow 6\geq 8$ , impossible. Where is my mistake?

-
Your hypothesis $n \geq a$ changes with $n$. In order for induction to work you need this to work for ALL $n$. Basically the part "which Yields that $n+1 \geq a ...$. What happens in this step if $n <a \leq (n+1)?$. How can you use P(n)? – N. S. Nov 3 '11 at 17:03
But your statement is true!!! – Tigran Hakobyan Nov 3 '11 at 18:36

First you said "$1\geq a$, which is true". Then you tried to apply it with $a=2$.

-
I don't see what you mean... I proved that the inequality holds for n=1 and then for every n>1. – nick Nov 3 '11 at 17:10
You only proved "the inequality holds for $n=1$" if $a \leq 1$ as well. – mt_ Nov 3 '11 at 17:15
Thank you very much!!! I get it now. One last thing: I tried to prove this in order to show that $\lim_{n \to \infty }\frac{a^n}{n!}=0$ Do you know an alternative way to do that? – nick Nov 3 '11 at 17:25
Fix $a>0$, let $m$ be the smallest whole number bigger than $a$. Let's only worry about values of $n$ bigger than $m$. Split $a^n/n!$ into two factors: the first $a^m/m!$ and the second whatever is left. The first factor is independent of $n$, i.e. it's a constant $C$ with respect to $n$. The second factor can be written $(a/n)(a/(n-1))...(a/(m+1))$. This is less than $a/n$, because all the other factors are less than one. So, $0\leq a^n/n! \leq aC/n$. This latter goes to zero with $n$. – mt_ Nov 3 '11 at 17:42

You only assumed that $n\ge a$. While it is indeed true that $n+1>n\ge a$ implies $n+1\ge a$, it fails in the case of $a=n+1$.

In such case $n+1\ge a$, but you can no longer use the claim with $n$ since $a>n$.

The proof is true if you fix $a$, but then $a\le 1$ since otherwise $a>1$ and the proof fails at some $n$.

-
"it fails in the case of a=n+1". How can a be greater than n? – nick Nov 3 '11 at 17:17
@nick: Did you fix $a$? If you fixed $a$ then the fact $1\ge a$ we have that $a^n\le1\le n$ anyway. If you claim that for every $n$, if $a\le n$ then $n!\ge a^n$, then coming to prove the claim for $n+1$ we have that since $a\le n+1$ is arbitrary, $a$ could be $n+1$. In such case we cannot use the case of $n$, since $a>n$. – Asaf Karagila Nov 3 '11 at 17:25
I understand... However, I only tried to prove this in order to show that $\lim_{n \to \infty }\frac{a^n}{n!}=0$ Do you know any other way to do that? – nick Nov 3 '11 at 17:29
@nick: Limits measure the asymptotic behavior, so you may need to start with $n$ which is large enough. For example, $n>2^a$ would probably be enough. – Asaf Karagila Nov 3 '11 at 17:41
Since it is actually a limit of a sequence I would say $n\geq \left [ 2^a+1 \right ]$ I can easily prove the rest. Thank you – nick Nov 3 '11 at 17:57

The problem is that $n \geq a \implies n! \geq a^n$ does not imply $n+1 \geq a \implies (n+1)! \geq a^{n+1}$. You just proved $( n\geq a \wedge n! \geq a^n) \implies (n+1)! \geq a^{n+1}$, which is true for $a \geq 0$.

You should state what set $a$ is coming from.

-

To be a bit more explicit: Your induction hypothesis is

For all $a\in\mathbb{R}_{\geq 0}$, if $n\geq a$ then $n!\geq a^n$.

You want to prove:

For all $b\in\mathbb{R}_{\geq 0}$, if $n+1\geq b$, then $(n+1)!\geq b^{n+1}$.

(I changed the letter to make it clearer; but of course that statement above is equivalent to one in which we have "$a$" instead of "$b$".

To prove the implication, you assume $n+1\geq b$. In order to apply the induction hypothesis, you would need $n\geq b$; if that holds, then your argument works: if $n\geq b$, then the induction hypothesis implies $n!\geq b^n$, and then multiplying by $n+1\geq b$ we get $(n+1)!\geq b^{n+1}$.

But what if we do not have $n\geq b$? The assumption $n+1\geq b$ does not guarantee this.

How could you find this out? Since you already know there is a counterexample, take your "inductive argument" out for a spin in the smallest counterexample. The smallest counterexample comes with $n=2$: assume $2\geq a$. Does it follow that $1!\geq a^1$? No; from $2\geq a$ you cannot conclude $1!\geq a$. In fact, if $2\geq a\gt \sqrt{2}$, you will have $a^2 \gt 2 = 2!$; the problem being that you don't get to apply that induction hypothesis on any $a$ greater than $1$ (and the conclusion fails for any $a$ greater than $\sqrt{2}$).

-