Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Nov 3, 2011 #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: Nov 3, 2011
  2. jcsd
  3. Nov 3, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    Re: False statement proven by induction? [tex]n\geq a\Rightarrow n!\geq a^n[/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]
     
  4. Nov 3, 2011 #3
    Re: False statement proven by induction? [tex]n\geq a\Rightarrow n!\geq a^n[/tex]

    I am sorry, I messed up with latex. That was not my hypothesis...
     
  5. Nov 3, 2011 #4

    Stephen Tashi

    User Avatar
    Science Advisor

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

    I was having trouble too. The world will probably end because of clerical errors.
     
  6. Nov 3, 2011 #5

    disregardthat

    User Avatar
    Science Advisor

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

    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.
     
  7. Nov 3, 2011 #6

    mathman

    User Avatar
    Science Advisor
    Gold Member

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

    The basic problem seems to be that allowed values of a increase with n, while induction would work only if a is constant.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: False statement proven by induction? [itex]n \geq a \Rightarrow n! \geq a^n[/itex]
  1. N /n! = ? (Replies: 21)

Loading...