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

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