C. Hinsley

12 August 2020

The Fibonacci sequence is defined as an infinite sequence beginning with the elements $0$ and $1$, for which each subsequent element is the sum of the two elements preceding it. In other words, the sequence can be defined in terms of a recurrence relation.

$$ F_0 = 0; F_1 = 1 $$

$$ F_{n+2} = F_{n+1} + F_n $$

Expanding the first 10 elements, we obtain the following.

$$ F = \{ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots \} $$

It turns out there is a closed-form solution to this recurrence relation, known as Binet's formula:

$$ F_n = \frac{\left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n}{\sqrt{5}} $$

It's not immediately obvious how this is derived, and most explanations are littered with distracting detours and descriptions that ought to be instead relegated to footnotes. Let's just get right down to how you can derive this formula yourself.

Let's start with the recurrence relation.

$$ \frac{F_{n+2}}{F_{n+1}} = \frac{F_{n+1} + F_n}{F_{n+1}} $$

$$ \frac{F_{n+2}}{F_{n+1}} = 1 + \frac{F_n}{F_{n+1}} $$

The following equality is fairly obvious, and is necessary to proceed further.

$$ \lim_{n \to \infty} \frac{F_n}{F_{n+1}} = \lim_{n \to \infty} \frac{F_{n+1}}{F_{n+2}} $$

This gives the following.

$$ \lim_{n \to \infty} \frac{F_{n+2}}{F_{n+1}} = 1 + \lim_{n \to \infty} \frac{F_{n+1}}{F_{n+2}} $$

We can set a constant $\gamma$ to simplify this equality.

$$ \gamma = \lim_{n \to \infty} \frac{F_{n+2}}{F_{n+1}} $$