1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A funny proof, but what is wrong with it?

  1. Apr 10, 2012 #1
    Here's a question:-

    Prove that for all positive integers n,

    [(n+1)/2]^n >= n!

    And here's a funny proof for it:-

    Assume to the contrary that, for all positive integers n,

    [(n+1)/2]^n < n!

    However, for n=2,

    (3/2)^2 > 2!

    Therefore, our assumption must be false.

    And hence, for all positive integers n, [(n+1)/2]^n >= n!

    Now, I know that this proof can't be correct, because I've seen the real proof, and it's a marvel, making use of algebraic inequalities, and the proof above simply seems too simple compared to it. But I wonder, what's the mistake with the above proof?
  2. jcsd
  3. Apr 10, 2012 #2
    You've made a logic mistake.

    Consider the sentence

    "All men are mortal"

    This is true. But what's the negation of this sentence?? Is it

    "All men are immortal"?

    or is it

    "There is a man that is immortal"??

    It's the second one.

    So, if your assertion is

    "For all natural numbers n holds the inequality blabla"

    then the negation of that is

    "There is a natural number n such that the inequality does not hold"

    Your proof shows that the inequality holds for n=2. But this does not contradict the negation, as there could still be an n such that it doesn't hold.
  4. Apr 10, 2012 #3
    The assumption that for all possible integers n, n!>[(n+1)/2]^n is violated by your counter example, so that demonstrates that your assumption is false. You have not checked all possible values of n so it says nothing about any of those values. Your assumption being false says nothing about the case of only some n's satisfying the inequality.
  5. Apr 11, 2012 #4
    Oh...now I understand. Thanks, micromass and bmxicle! :D
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook