The statement doesn't make sense for n=0 !

We'll prove it for every natural number n>0 by induction on k.

Base case: k=1.

iff iff and this is true for every n>0.

iff and this is true for every n>0.

Base case verified.

Let for arbitrary n>0

(1)

hold for some 0<k<n . We want to show that (1) also holds for k+1, i.e. we want

(2)

to hold.

From the second inequality in (1) we have and this is strictly less than iff which is equivalent to which is true because n>0.

So the second inequality in (2) is verified.

From the first inequality in (1) we have and this is strictly greater than iff

which is equivalent to .

Now because k<n we have , no doubt.

So the first inequality in (2) is also verified and thus the induction step is completed and the proof is finished.