Lesson 1

In this section, we develop a method for solving a wide class of recurrence relations—linear recurrence relations. The recurrence definition of Fibonacci numbers is a prominent example of this class. Below, we will derive Binet’s formula for them and then generalize the ideas of this derivation. \[F(n)=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right) \ .\]