Prove
where and
is the greatest integer less than or equal to
.
Proof. The proof is by induction. For the case

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
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.
Never mind. Disregard! Major mistake in the last step of my “proof”.
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
.
I of course meant powers:
I think you’re right.
Maybe you can try to prove (n+1)^n >= 2n^n or (1+ 1/n)^n >= 2. (Use Bernoulli’s Inequality here).
Then in the inductive step:
(n+1)!/(n+1)^(n+1) = n!/(n+1)^n <= n!/(2n^n) .
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