Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

4 Answers 4

up vote 3 down vote accepted

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

share|improve this answer
    
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
1  
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
1  
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$.

share|improve this answer
    
"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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.