We use the following recursive definition of the Fibonacci numbers,

Prove that for all we have,

*Proof.*For the case , we have and

So, the inequality is true for . Assume then that the inequality is true for some . Then,

But, as one can compute, . Hence,

Thus, the inequality holds for all