thesublimeblog

“Rabbit Math” – A Formula for the Magical Fibonacci Sequence

You don’t have to be a mathematician to appreciate the wonderful symmetry of some mathematical formula. Here’s one formula I am especially fond of. It’s called Binet’s formula for the nth term of a Fibonacci sequence. The formula is named after the French mathematician and physicist, Jacques Philippe Marie Binet (1786 – 1856) who made fundamental contributions to number theory and matrix algebra.

Binet’s Formula

\displaystyle F_n=\frac{1}{5} \bigg\{ \bigg(\frac{1+\sqrt5}{2} \bigg)^n - \bigg(\frac{1-\sqrt5}{2} \bigg)^n \bigg\}

There are three reasons why I’m enchanted by this formula. First, it relates to the intriguing Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, etc. which captures a distinctive growth pattern. In its original appearance in the 13th century publication by Leonardo of Pisa (also known as Leonardo Fibonacci), this growth pattern was that of a rabbit population. The following passage, translated from Leonardo’s book reads:

In the first month, start with a pair of baby rabbits. One month later, they have grown up. The following month, the pair of grown rabbits produce a pair of babies, so now we have one pair of grown rabbits and one pair of baby rabbits. Each month thereafter, each pair of grown rabbits produce a new pair of babies, and every pair of baby rabbits grows up. How many pairs of rabbits will there be at the end of one year?

Well, the answer to that question is 233 pairs of rabbits (i.e., after the 12th month is completed). Rabbit problems have intrigued people ever since. More seriously, they have found many applications in many areas of computer science such as search algorithms and cryptography.

The second reason why I am fascinated with Binet’s formula is that the famous Golden Ratio is explicit in the formula. Due to its symmetry properties, this ratio has shaped art and architecture throughout human history. The Golden Ratio is the expression for \alpha in the formula, where \displaystyle \alpha = \frac{1+ \sqrt5}{2} = 1.618034.

Thirdly, because the Fibonacci sequence grows very quickly, the nth term for large n is a very huge number. For example, the 31st term is already larger than one million. By the time we reach the 45th term, there are more than one billion pair of rabbits! So it is nice to have a formula that gives an accurate answer for nth term of the Fibonacci sequence relatively quickly. This is exactly what Binet’s formula does.

For these reasons, I really think that Binet’s formula is super cool. Not only is it beautiful to look, it is also practical.

For those who are curious, two questions arise: first, how did Binet’s formula came about? And second, is it connected to number series other than the Fibonacci sequence? In the rest of this blog, I will attempt to answer both questions. Note: if you don’t feel like going any further, skip the rest of the post. You already had the pleasure of seeing an elegant formula, arguably one of the most famous in number theory.

Let’s proceed to clear the mystery of how Binet’s formula came about. I’ll start from the beginning. The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, ... and its generating function is

\displaystyle F(x) = F_1(x) + F_2x^2 + F_3x^3 + F_4x^4 + f_5x^5 + ...

= \displaystyle x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 ... + \hspace{320pt} (1)

where the coefficient of the terms involving x are the elements of the Fibonacci sequence (ignoring the first term, zero).

The Fibonacci sequence is an example of a recursive function, where

\displaystyle F_n = F_{n-1} + F_{n-2}

thus giving F_3 = 1 and F_4 = 2 nd so on.

Making use of the recursive function, and after some algebra, we can show that

\displaystyle F(x) = x + x^2 F(x) + xF(x)

This gives us an equation where we can solve for F(x) to obtain the beautiful formula for the Fibonacci generating function:

\displaystyle x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + ... = \frac{x}{1-x-x^2}

The denominator \displaystyle 1 - x - x^2 is a polynomial whose roots are \displaystyle \frac{-1 \pm \sqrt 5}{2} which in turn are the reciprocals of the two numbers

\displaystyle \alpha = \frac{1+\sqrt 5}{2} \ \mbox{and} \displaystyle \beta = \frac{1-\sqrt 5}{2} \hspace{320pt} (2)

Next, we use the idea of partial fractions to split the function \displaystyle \frac{x}{1-x-x^2} into the sum of two pieces as follows:

\displaystyle \frac{x}{1-x-x^2} = \frac{A}{1-\alpha x} + \frac{B}{1-\beta x}

After some manipulations, we find that

\displaystyle A = \frac{1}{\alpha - \beta} \ \mbox{and} \displaystyle \frac{B}{\beta - \alpha}

Substituting the values for \alpha and \beta from (2) into the above expression, we have

\displaystyle A = \frac{1}{\sqrt 5} \ \mbox{and} \displaystyle B = -\frac{1}{\sqrt 5}

This allows us to factor the polynomial as

\displaystyle 1-x-x^2 = (1-\alpha x)(1- \beta x)

Thus, \displaystyle F(x) = \frac{x}{1-x-x^2} can be written as

\displaystyle \frac{x}{1-x-x^2} = \frac{1}{\sqrt 5} \bigg( \frac{1}{1-\alpha x} \bigg) - \frac{1}{\sqrt 5} \bigg( \frac{1}{1-\beta x} \bigg) \hspace{250pt} (3)

At this juncture, another number sequence – the geometric series – comes into the picture. The geometric series is \displaystyle 1+x+x^2+x^3+x^4 + ... . It converges to \displaystyle \frac{1}{1-x} . Similarly,

\displaystyle \frac{1}{1- \alpha x} = 1+\alpha x + (\alpha x)^2 + (\alpha x)^3 + (\alpha x^4) + ...,

\displaystyle \frac{1}{1- \beta x} = 1+\beta x + (\beta x)^2 + (\beta x)^3 + (\beta x^4) + ...,

Substituting these two expressions into (3) allows us to write \displaystyle F(x) = \frac{x}{1-x-x^2} as a power series

\displaystyle \frac{x}{1-x-x^2} = \frac{\alpha - \beta}{\sqrt 5} x + \frac{\alpha^2 - \beta^2}{\sqrt 5} + \frac{\alpha^3 - \beta^3}{\sqrt 5} x^3 + ...

But we know from (1) that \displaystyle \frac{x}{(1-x-x^2)} is the generating function for the Fibonacci sequence \displaystyle F(x) = F_1(x) + F_2x^2 + F_3x^3 + F_4x^4 + f_5x^5 + ... . Therefore, matching the two series for \displaystyle \frac{x}{(1-x-x^2)} , we find that

\displaystyle F_1 = \frac{\alpha-\beta}{\sqrt 5}, \ F_2 = \frac{\alpha^2 - \beta^2}{\sqrt 5}, \ F_3 \frac{\alpha^3 - \beta^3}{\sqrt 5}

Since we know that \alpha = \frac{1+\sqrt 5}{2} \ \mbox{and} \beta = \frac{1-\sqrt 5}{2} , the general equation for the nth term of F(x) is therefore

\displaystyle F_n = \frac{1}{\sqrt 5} \bigg\{ \bigg(\frac{1+\sqrt 5}{2} \bigg)^n - \bigg(\frac{1-\sqrt 5}{2} \bigg)^n \bigg\}

Bravo! We have cleared the mystery of how Binet’s formula came about. Along the way, we saw that it made contact with the geometric series which pops up in many scientific and finance applications.

Further reading

Joseph H. Silverman, A Friendly Introduction to Number Theory, Pearson, 4th ed., 2014.

Leave a Reply