Let fn be the nth Fibonacci number.
We will prove by strong mathematical induction that 2n>fn.
Base case:
f0=0<20, f1=1<21.
Induction step:
Assume fk<2k for all k≤n, then
fk+1=fk+fk−1<2k+2k−1<2⋅2k=2k+1
So, the inequality fn<2n is true for n=k+1, thus, by strong mathematical induction fn<2n for all n≥0 and fn<2n<en.
Hence
fn+1−fn=fn−1<2n−1<2n=2n+1−2n<en(e−1)=en+1−en.
Comments
Leave a comment