**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 .

F_{n} 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 F_{n} is done here’s the proof by induction.

Perform the induction step:

Assume:

Because

The proof that is straightforward.

for example and

Clearly for n>30 is a good approximation.

n | approx | exact | epsilon |

0 | 0.4472135955 | 0.894427191 | 0.4472135955 |

1 | 0.72360679775 | 0.4472135955 | 0.27639320225 |

2 | 1.17082039325 | 1.3416407865 | 0.17082039325 |

3 | 1.894427191 | 1.788854382 | 0.105572809 |

4 | 3.06524758425 | 3.1304951685 | 0.0652475842499 |

5 | 4.95967477525 | 4.9193495505 | 0.0403252247502 |

6 | 8.0249223595 | 8.049844719 | 0.0249223594996 |

7 | 12.9845971347 | 12.9691942695 | 0.0154028652506 |

8 | 21.0095194942 | 21.0190389885 | 0.00951949424901 |

9 | 33.994116629 | 33.988233258 | 0.00588337100159 |