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.
The solutions of the quadratic
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...