Home » Blog » Prove an inequality on the ratio of n! to the nth power of n

# Prove an inequality on the ratio of n! to the nth power of n

Prove where and is the greatest integer less than or equal to .

Proof. The proof is by induction. For the case we have on the left, On the right, we have since implies (since 1 is the greatest integer less than or equal to ).
Assume then that the inequality is true for some . Then, But, from part (b) of this exercise we have for all (and, in particular, must hold for , which will use in the following). So, Thus, we plug this back in to the inequality above and have, Notice that the inequality we have arrived at as as opposed to the we want. This is to deal with the fact that is the greatest integer in . This takes care of that problem since to complete the proof by induction we need to show that if the inequality holds for , then it holds for . If is even, then and . On the other hand, if is odd, then . In either case though we have, , so Hence, the inequality holds for the case if it is true for any .
Thus, the inequality is true for all 1. richardsull says:

Here’s a proof that I think is a little cleaner:

For the inductive step, notice that where k is the greatest integer less than or equal to n/2 (which I'll write as [n/2]).

When n is even, k = [n/2] = [(n+1)/2], and the inductive step is proven.

When n is odd, [(n+1)/2] = [n/2] + 1 = k + 1, so we can write and the inductive step is proven for odd n as well.

• richardsull says:

Never mind. Disregard! Major mistake in the last step of my “proof”.

2. Artem says:

The part of inequality when m is even is probably wrong. First of all in this case , not . However, is odd, so you have to prove that the left part is actually smaller than , not anyways. You first proof makes it possible for the .

• Artem says:

I of course meant powers: • Long Vo says:

I think you’re right.

3. Scott says:

Maybe you can try to prove (n+1)^n >= 2n^n or (1+ 1/n)^n >= 2. (Use Bernoulli’s Inequality here).

• Scott says:

Then in the inductive step:
(n+1)!/(n+1)^(n+1) = n!/(n+1)^n <= n!/(2n^n) .

4. Ed says:

Notice that the inequality we have arrived at as (1/2)^{k+1} as opposed to the (1/2)^k we want. This is to deal with the fact that k is the greatest integer in m/2. This takes care of that problem since to complete the proof by induction we need to show that if the inequality holds for m, then it holds for m+1. If m is even, then k = m/2 and k+1 = (m+1)/2+1/2. On the other hand, if m is odd, then k = (m-1)/2 and k+1= (m+1)/2 In either case though we have, k+1 \geq (m+1)/2