Chapter 0: Section 0.1 - Part 1
1. "It is not difficult to find a formula for Fn" (1) The standard recurrence relation for Fibonnaci number n is: F0=0 F1=1 For n≥2 Fn=Fn−1+Fn−2 (2) The formula for n is as follows: Fn=1√5((1+√52)n−(1−√52)n) 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 F1=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 ...