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

Proof by induction: help

  1. Nov 24, 2006 #1
    i have to prove by induction that n2 < n! for n > 3

    this is what i have done:

    the base case (n = 4) is obviously true since 42 < 4!

    now, assume that it is true for n = k, i.e., k2 < k!

    now i have to prove it for n = k+1

    since k > 3,
    1 < k-1
    1(k+1) < (k-1)(k+1)
    k+1 < k2 - 1 < k2 < k!
    k+1 < k!
    (k+1)(k+1) < (k+1)k!
    (k+1)2 < (k+1)!

    what i have done seems ok to me. but is there any simpler way to do the induction step? what i have done seems a bit "forced" (if you know what i mean).

    thanks in advance.
  2. jcsd
  3. Nov 24, 2006 #2
    The steps you take seem correct. A bit simpler way is to think of what you want to prove: (k+1)2<(k+1)! and by using equivalent relations to simplify it, like this for example:

    (k+1)(k+1)<k! (k+1)<=> *note k+1>0*

    We know that k2<k! so we just have to prove that k+1<k2, which is easy because k(k-1)>1 for any k>3
    Last edited: Nov 24, 2006
  4. Feb 4, 2012 #3
    I'm not a big fan of this particular inductive proof, since I've never found a short argument that didn't require me to manipulate both sides of the inequality like that. I've seen a similar proof on www.inductiveproofs.com that is 2^n < n! -- maybe that one will provide some inspiration.
  5. Feb 5, 2012 #4
    Thereis no simpleway of doing this . For all mathematcialproof by inductionyou must assume p(k) is true and then prove p(K+1) is true for all n =1,2..... which you haveseem tobe done any way
  6. Feb 5, 2012 #5


    User Avatar
    Science Advisor

    i know exactly what you mean. the trouble is, for n < 4, the theorem simply isn't true:

    12 = 1! = 1
    22 > 2! = 2
    32 > 3! = 6

    and it's not like for n = 3, we have equality, or that 32 is "just barely" more than 3!, the break-even point is somewhere between 3 and 4 (if you were using the gamma function, for example). so when we get to the part where we use n > 3:

    1 < k-1

    it's not "elegant", we prove something a little stronger than we need (after all, k = 3 would make that statement true, but then our "base case" fails).

    this often happens with inequalities, the bounding term is often something that is more than "just barely greater than".

    i wouldn't worry over-much about this, your proof is clear, clean, and well-reasoned. there's bigger molehills to make into mountains, if you're into that sort of thing.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook