# Math Induction

1. Sep 21, 2010

### rival95

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. Sep 21, 2010

### Simon_Tyler

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
3. Sep 21, 2010

### Simon_Tyler

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.