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}.

Advertisements

Published by

William Kuszmaul

I am an MIT Ph.D. student in the computer science department. My research focuses on algorithms and combinatorics.

One thought on “Fibonacci Formulas For Fantastic Fun”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s