# Fibonacci Formulas For Fantastic Fun

The Fibonacci numbers are the sequence ${1, 1, 2, 3, 5, 8, \ldots}$, and satisfy the recurrence ${F(n) = F(n - 1) + F(n - 2)}$. They also have a beautiful formula,

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

This seemingly complicated formula actually has a very simple explanation.

Consider the set ${V}$ of number sequences of the form ${a_1, a_2, \ldots}$ that satisfy the recurrence ${a_n = a_{n - 1} + a_{n - 2}}$. I call the set “${V}$” because it turns out to form a vector space. That is, given any two sequences ${a_1, a_2, a_3, \ldots}$ and ${b_1, b_2, b_3, \ldots}$ in ${V}$, their sum ${(a_1 + b_1), (a_2 + b_2), \ldots}$ satisfies the same Fibonacci-style recurrence as they do, as does any scalar multiple of ${a_1, a_2, a_3, \ldots}$.

Notice that ${V}$ is not, however, a very complicated vector space. Because each number sequence in ${V}$ satisfies the Fibonacci-recurrence, each number sequence is entirely determined by its first two entries. Consequently, ${V}$ has dimension two.

If you look at the first few terms of the Fibonacci numbers, you might notice that they seem to grow at a roughly exponential rate. Consequently, one might hope that ${V}$ has a two basis elements of the form ${1, a, a^2, a^3, \ldots}$ and of the form ${1, b, b^2, b^3, \ldots}$. Indeed, if ${V}$ did, then we would get for free that, for some constants ${c_1,c_2 \in \mathbb{R}}$,

$\displaystyle F(n) = c_1 a^n + c_2 b^n.$

Fortunately, such ${a}$ and ${b}$ do exist and are easy to find. In order for ${1, a, a^2, \ldots}$ to satisfy the recurrence ${a^n = a^{n -1} + a^{n - 2}}$, we need that ${a^2 = a + 1}$. Applying the quadratic formula, we get values for ${a}$ and ${b}$,

$\displaystyle a = \frac{1 + \sqrt{5}}{2},$

$\displaystyle b = \frac{1 - \sqrt{5}}{2}.$