False statement proven by induction? [itex]n \geq a \Rightarrow n! \geq a^n[/itex]

  • #1
I will prove the false statement, that [tex]n\geq a\Rightarrow n!\geq a^n, n\in \mathbb{N}-\left \{ 0 \right \}[/tex] with induction

For [tex]n=1[/tex] [tex]1\geq a\Rightarrow 1!\geq a^1\Rightarrow 1 \geq a[/tex] which is true.

Suppose that [tex]n\geq a\Rightarrow n!\geq a^n, n\in \mathbb{N}-\left \{ 0 \right \}[/tex]

Then,
[tex]n\geq a\Rightarrow (n+1)!\geq nn!\geq aa^n=a^{n+1}[/tex] which yields that [tex]n+1\geq a\Rightarrow(n+1)!\geq a^{n+1}[/tex]

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

[EDIT] Don't bother answering. I have highlighted the mistake I made that rendered the inequality invalid for a greater than 1
 
Last edited:

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,583
1,472


Suppose that [tex]n\geq a\Rightarrow n!\geq a^n, n\in \mathbb{N}-\left \{ 0 \right \}[/tex]
That's not the hypothesis used in induction.

Ordinary induction would use the hypothesis:
[itex] n!\geq a^n [/itex] where we think of [itex] n [/itex] as a particular integer, not as "all integers".

and you would have to prove [itex] (n+1)! \geq a^{n+1} [/itex]

So-called "strong induction" would use the hypothesis:
For each integer [itex] i: 0 < i \leq n , i! \geq a^i [/itex]

and you would still have to prove [itex] (n+1)! \geq a^{n+1} [/itex]
 
  • #3


That's not the hypothesis used in induction.

Ordinary induction would use the hypothesis:
[itex] n!\geq a^n [/itex] where we think of [itex] n [/itex] as a particular integer, not as "all integers".

and you would have to prove [itex] (n+1)! \geq a^{n+1} [/itex]

So-called "strong induction" would use the hypothesis:
For each integer [itex] i: 0 < i \leq n , i! \geq a^i [/itex]

and you would still have to prove [itex] (n+1)! \geq a^{n+1} [/itex]
I am sorry, I messed up with latex. That was not my hypothesis...
 
  • #4
Stephen Tashi
Science Advisor
7,583
1,472


I was having trouble too. The world will probably end because of clerical errors.
 
  • #5
disregardthat
Science Advisor
1,861
34


The problem is that [itex]n+1 \geq a[/itex] does not imply that [itex]n \geq a[/itex] which you seem to have used.
 
  • #6
mathman
Science Advisor
7,904
461


The basic problem seems to be that allowed values of a increase with n, while induction would work only if a is constant.
 

Related Threads on False statement proven by induction? [itex]n \geq a \Rightarrow n! \geq a^n[/itex]

Replies
11
Views
3K
  • Last Post
Replies
1
Views
2K
Replies
6
Views
1K
Replies
2
Views
655
Replies
8
Views
2K
Replies
9
Views
1K
Replies
8
Views
3K
Replies
5
Views
953
Top