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!

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