for all ....(*)
by mathematical induction.
Note that I have changed the less-than in the original statement to less-than-or-equal. Otherwise (*) would be false when r=0.
I'm going to assume you know the important identity .
First check the case :
If then the only possible value of r is .
and , so (*) is true.
Now suppose that for some integer k we have
for all .
I will let you check the case .
If then , so by assumption we also have
Adding the two inequalities,
so by the identity stated above,
so (*) holds for
By mathematical induction, (*) is true for all .