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

Math Induction

  1. Sep 21, 2010 #1
    Trying to solve a question, but having a hard time starting it.

    Question:
    (n/3)^n < n! < (n/2)^n ; all integers n > 5

    I proved the base case already and made the assumption of P(k) and am having difficulty knowing where to start on my proof of:

    P(k+1): ( (k+1)/3)^k+1 < (k+1)! < ( (k+1)/2)^k+1

    any help is greatly appreciated.
     
  2. jcsd
  3. Sep 21, 2010 #2
    Here's a possible method that is not induction:

    (n/2)^n > 1 for n > 2.
    (n/3)^n > 1 for n > 3.

    So for n > 3 we can take the Log of the inequality.
    Log((n/3)^n) < Log(n!) < Log((n/2)^n)

    For n large enough (to be determined) we can use Stirling's approximation
    Log(n!) ~ (-1 + Log(n)) n + O(1)

    Then cancel out the common (positive) factor of n in the inequality and remove the Log(n) term from each side to get
    -Log(3) < -1 < -Log(2)
    which is true.

    All that remains to be shown is that Stirling's approximation is good enough for integer n>5.
     
    Last edited: Sep 22, 2010
  4. Sep 21, 2010 #3
    Actually, a proof by induction is not too hard either.
    But as this is your first post to these forums I suspect it's a homework problem.
    So I won't give you the proof yet.

    I found it by starting with the n+1 inequality:
    ((n + 1)/3)^(n + 1) < (n + 1)! < ((n + 1)/2)^(n + 1)
    and noting that it implies
    1/3 ((n + 1)/n)^n (n/3)^n < n! < 1/2 ((n + 1)/n)^n (n/2)^n

    Now you just need to play with the ((n + 1)/n)^n factors.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook