Fibonacci Numbers. The Fibonacci numbers are
1,1,2,3,5,8,13,21,….
We can define them inductively by f1=1, f2=1, and fn+2=fn+1+fn for n∈N.
((a)) Prove that fn<2n.
((b)) Prove that fn+1fn−1=fn2+(−1)n, n≥2.
((c)) Prove that fn=[(1+5)n−(1−5)n]/2n5.
((d)) Show that ϕ=limn→∞fn+1/fn=(5+1)/2. The constant ϕ is known as the golden ratio.
((e)) Prove that fn and fn+1 are relatively prime.
Hint. For (a) and (b) use mathematical induction. (c) Show that f1=1, f2=1, and fn+2=fn+1+fn. (e) Use part (b) and Exercise 2.4.16.