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

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) .

Very brief proof of (n+1)^n >= 2n^n: notice that the first two terms of (n+1)^n are n^n and n*n^(n-1)=n^n, ie 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