Chapter 0: Section 0.1 - Part 1
1. "It is not difficult to find a formula for $F_n$" (1) The standard recurrence relation for Fibonnaci number $n$ is: $F_0 = 0$ $F_1 = 1$ For $n \ge 2$ $$F_n = F_{n-1} + F_{n-2}$$ (2) The formula for $n$ is as follows: $$F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$ Notes: The formula is known as Binet's Formula and its derivation showcases the deep relationship between the Fibonacci number and the golden ratio . The derivation and elementary proofs are detailed here . Exercises: 1. Exercise 0.1.1: (a) Use the recurrence relation for the fibonacci numbers, and induction to prove that every Fibonacci number is an integer. Solution: S(1) is true since $F_1 = 1$ is an integer. We assume that S(k) is true, that is, S(k) is an integer. S(k+1) = S(k) + S(k-1) which is an integer since the sum of two integers is an integer by the closure property on addition. See here for properties of integers. 2