display | more...

Binet's formula is a formula for the nth Fibonacci number. Let

```           1 + √5
φ1 := ------,
2

1 - √5
φ2 := ------,
2
```

be the two golden ratios (yeah, there's two if you allow one of them to be negative). Then the nth Fibonacci number (with 1 and 1 being the first and second numbers) is

```            φ1n - φ2n
B(n) = ---------.
√5
```

I first encountered this formula in my first ever mathematics undergraduate course. It was actually, of all places, in a calculus class, if you really must know. It's a very surprising formula. It involves an algebraic combination of three irrational numbers, amongst which is a division, and it nevertheless yields integers (the Fibonacci numbers) for all natural n. It's also rather surprising that it exists at all. It's very easy to come up with sequences of natural numbers for which no known formula exists (and sometimes, we can even prove that no formula of certain type could exist). A formula for the nth prime number, a formula for the number of partitions of an integer n, a formula for the number of isomorphism classes of finite groups of order n... None of these are known and most likely will never be, and yet, the Fibonacci numbers, with all of their wondrous and seemingly inexhaustible surprises (they have their own journal after all, The Fibonacci Quarterly), have yet another surprise for us: they have a relatively simple formula that describes them.

It's not difficult at all to prove by induction that the formula works. The two base cases for n = 1 and 2 are trivial to verify, and the induction step is simply to compute that B(n) + B(n+1) = B(n + 2), using the fact that that φ1 and φ2 are roots of the polynomial x2 - x - 1 (factor out n φ's and voilà). This in particular also proves that the formula must yield integers, since it yields Fibonacci numbers.

A neat thing about Binet's formula is that knowing a modicum of mathematics beyond high school level yields some interesting facts. For one, this knowledge allows one to come up with several interesting ways of deriving the formula. I shall present three below. As another application, here is what seems like an "obvious" way for someone with some knowledge of mathematics to know that Binet's formula yields integers.

#### Ridiculously high-powered method to show Binet's formula yields integers

We will need a few facts and definitions. Definition the first: an algebraic integer is the root of a monic polynomial with integer coefficients. Fact the first: algebraic integers form a ring. Fact the second: If an algebraic integer is rational, then it must be an ordinary integer (zero, one, two, three, and their negatives). Fact the third (from elementary Galois theory, the theory formerly known as the theory of symmetric functions and permutations): a symmetric function of the roots of a polynomial takes values in the field to which the coefficients of the polynomial belong. In particular, a symmetric function of the roots of a polynomial with integer coefficients must take rational values.

All of these facts are common tools in the arsenal of most any mathematician. It's a simple task to piece them together to prove that Binet's formula yields integers. We have already observed that φ1 and φ2 are roots of a monic polynomial with integer coefficients; i.e. they are algebraic integers. Next, Binet's formula can be rewritten

```             φ1n - φ2n
B(n) =  ---------
φ1 - φ2
```

from which it is clear that it's a symmetric function of φ1 and φ2. Hence, B(n) must be a rational number for all n. Lastly, we observe that φ1n - φ2n factors and cancels with the denominator in B(n), so that B(n) must be an algebraic integer as the combination of sums and products of two algebraic integers. Since it's a rational algebraic integer, it must be an ordinary integer. QED.

## Some divinely inspired methods to derive Binet's formula

I got the inspiration for this writeup when Timeshredder asked me (a long, long time ago) about a mathematical idea or problem that a highschooler could easy understand but could hardly solve, while an undergrad mathematician could solve after scratching her head for a few moments. Binet's formula seems like just such an idea.

The Hungarian-born mathematician and educator George Pólya used to say something about a theorem's importance being inversely proportional to how hard it is to state and directly proportional to how hard it is to prove, as well as to the amount of surprise involved in the proof. Binet's formula seems to scale high on the importance scale by a pleasantly surprising modification of this criterion: instead of being difficult to prove (it's not, the proof is the induction I gave above), it's difficult to come up with it.

Below I shall give a few methods for deriving the formula (which by the way of derivation will also prove its correctness). I do not know how Binet or whoever really came up with the formula first dreamed it up. These stories are often fascinating, for it is not unusual to hear accounts of remarkable serendipity in mathematics. Here are three possible divine inspirations that once you stumble upon them, Binet's formula blossoms as a side result.

### Divine inspiration the first. A recurrence relation is like a differential equation.

For the first seemingly magical method for deriving Binet's formula, we draw an analogy between linear ordinary differential equations and difference equations. A differential equation yields a solution that we often think of as some quantity that is varying in time; a difference equation could be thought of as an equation whose solution we only know at discrete points in time, not throughout a whole interval of time. Each term of a sequence of integers can be thought of as one of those discrete time instants in which we know the solution.

Thus, the defining difference equation of the Fibonacci numbers,

an+2 = an+1 + an

Makes us think of the differential equation

f'' = f' + f

where the fact that the first two Fibonacci numbers are 1 and 1 can be interpreted as the initial conditions of the differential equation cum difference equation. We note that the differential equation that the Fibonacci numbers inspire is a constant-coefficient linear differential equation. By a fundamental theorem of ordinary differential equations, we know that such equations should have a vector space of solutions, in this case of dimension two since the equation is of order two. That is, we should be able to find two linearly independent solutions, and then obtain the specific solution by using the initial conditions a1 = a 2 = 1. That part of the theory only depends on the linearity and constant-coefficientness of the equation, a linearity that the difference equation also has, and thus the same method should apply. It can be shown that indeed it does, and the difference equation will have at most two linearly independent solutions in the vector space of numerical sequences.

By classical theory of ordinary differential equations, we also know that exponentials are a good guess for finding these two fundamental linearly independent solutions. Thus we postulate that ek n could be a solution giving the nth term of the Fibonacci difference equation for some suitable k, which leads to the equation

ek(n + 2) - ek(n +1) - ek = 0

or

ekn(e2k - ek - 1) = 0.

This product can only be zero if and only if the second trinomial factor is zero, since an exponential can never be zero. If we let r := ek, we recognise that this trinomial factor is a quadratic in r and that our proposed fundamental solution to the difference equation is now rn.

r2 - r - 1 = 0

are r = φ1 and r = φ2, the two golden ratios. Thus our fundamental solutions are φ1n and φ2n, and the solution of the Fibonacci sequence, given the initial conditions that the first two numbers must be 1, must be a linear combination of them. Hence, the inital condition gives us the linear system of equations,

aφ1 + b φ2 = 1
aφ12 + bφ22 = 1.

Upon solving this system for a and b we discover that a = 1/√5 and b = -1/√5 which is exactly Binet's formula.

### Divine inspiration the second. A linear recurrence comes from a linear transformation. Find that transformation.

This time we exploit the linearity of the Fibonacci recurrence more directly and invoke linear algebra. Since the Fibonacci recurrence involves the previous two terms at once, we shall describe it linear-algebraically with two-dimensional vectors

```          [  an  ]             [  1  ]
fn = [      ] ,     f1 =  [     ]
[ an+1 ]             [  1  ]
```

so that Fibonacci's recurrence can be stated as

fn + 1 = A fn

for some suitable matrix A, or,

fn = An - 1 f1.

An instant of thought reveals that the matrix A for the Fibonacci recurrence must be

```         [ 0  1 ]
A = [      ],
[ 1  1 ]
```

and the problem reduces to finding the powers of this matrix in order to find the fn of the sequence. Now, we know that diagonalised matrices are easy to raise to powers, since if A = SDS-1 with D diagonal, then An is easily seen to be SDnS-1, and raising a diagonal matrix to powers simply involves raising each element of the diagonal to that power. I will not cover here the computations necessary to carry out this matrix diagonalisation, but it should come as no surprise that the eigenvalues of A being raised to powers will again be our old friends, the golden ratios φ1 and φ2, and that after performing the necessary computations of S and S-1, we will again recover Binet's formula from fn = An - 1 f1. Since I do not think these routine calculations elucidate anything, I leave them to the diligent reader.

### Divine inspiration the third. A sequence of integers has a generating function. Use it.

Any modern mathematician will sooner or later instinctively write down the generating function of an integer sequence (or any kind of sequence) in hopes of coming up with information about the sequence. Concretely, for a sequence a0, a1, a2, ..., their generating function is

f(x) = a0 + a1x + a2x2 + a3x3 + ...

Examples of generating functions occur in probability theory with the moment generating function (which happens to be a Laplace transform) or the probability generating function. Generating functions are so common and useful that a pleasant but cheekily titled book on generatingfunctionology by H.S. Wilf exists. To a modern mathematician, considering the generating function of a sequence seems very natural, and this is a particularly useful technique in combinatorics where integer sequences abound.

The generating function of the Fibonacci numbers is of course,

f(x) = 1 + x + 2x2 + 3x3 + 5x4 + 8x5 + ...

Which we shall write as

```            ∞
-----
\
f(x) = >     an+1 xn.
/
-----
n=0
```

Now we seek to discover things about f(x). Although questions of convergence of the power series definition of f(x) can be satisfactorily addressed, they cloud the main points of the discussion, so we shall ignore them. They are largely irrelevant, since generating functions can be treated as purely formal power series and it can be shown that such formal treatment yields correct results.

Observing that multiplication by x of a generating function is equivalent to shifting the coefficients by one position to the right, we see that in terms of the generating function f(x), the defining equation of the Fibonacci numbers can be stated as

f(x) = xf(x) + x2f(x ) + 1.

Notice we had to add 1 in order to account for the first term of f(x). This is how this method accounts for the fact that a1 = a2 = 1. Now, solving for f(x), we obtain that

```               -1
f(x) = ----------.
x2 + x - 1
```

If we expand in partial fractions, we obtain

```             1  /   1           1  \
f(x) = ---(  ------  -  ------ ),
√5  \ x + φ1     x + φ2 /
```

where our old friends, the two golden ratios, have already surfaced. Next we expand the two fractions inside the bracket with a geometric series expansion, which yields

```                      ∞
/ ----                              \
1   /  \                                  \
f(x) = -- -(    >    (-1)n (φ1-n-1 - φ2-n-1) xn      ).
√5   \  /                                  /
\ ----                              /
n=0
```

Finally, we perform a number of simplifications, using the fact that φ1φ2 = -1, so that in particular 1/φ1 = -φ2, which finally gives

```               ∞
----     /                \
\       /   φ1n+1 - φ2n+1    \
f(x) =   >     (    -------------   ) xn.
/       \        √5        /
----     \                /
n=0
```

We recognise Binet's formula again as an expression giving the coefficients of f(x), the Fibonacci numbers.

QED, as they say...