Exercise 1.13: Prove that Fib(n) is the closest integer to n/5, where . Hint: Let Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that .
Fn is a linear second-order recurrence with constant coefficients. The characteristic equation for it is:
This means that the closed form solution is of the form
The constants and are determined by the initial conditions bellow.
The closed expression has the following form:
Now that the derivation of the closed form for Fn is done here’s the proof by induction.
Perform the induction step:
The proof that is straightforward.
for example and
Clearly for n>30 is a good approximation.