#2. Fibonacci Numbers, the Formula

(Back to course page.)

Link to slides · Link to recording

---

Prompts for discussion:

Exercise 1. Show that: $$F_n=\left\lfloor\frac{1}{\sqrt{5}} \cdot\left(\frac{1+\sqrt{5}}{2}\right)^n\right\rfloor$$

(Source: generatingfunctionology, Wilf; h/t Matthew Drescher and John Azariah for a fun Twitter discussion on this.)

Exercise 2. Use this method to work out a closed form for:

$$y_{n+2}=2 y_{n+1}-y_n$$

(Source: This is an exercise from the book.)