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

Question

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?

Answer 1

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

Answer 2

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$.

Answer 3

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.

Answer 4

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}$).