Colin Mitchell

Suppose
that two rabbits are born at _{}, produce two rabbits at _{}, and another two rabbits at each _{} after that. Also suppose that the rabbits never die. If
we let _{} denote the number of
pairs of rabbits at time *t*, then we
know that at months 0 and 1, we have one pair of rabbits. At month 2, these rabbits produce a pair,
which gives us three pairs. At month 3,
we have the original pair, their first off-spring, and another pair created by
the original offspring, which gives us three pairs. At month 4, the original pair have created three pair, and the pair born at month 2 have
created their own, which gives us five pair.
At month 5, the original pair have bore 4 pair, the rabbits born at
month 2 have born two pair, and the rabbits born on month 3 have bore a pair,
so this gives us 8 pairs of rabbits. We
can write this as

_{}

and generalize it as

_{}.

This is the Fibonacci Sequence. We want a
closed form for *n*. Consider the
linear difference equation

_{}

If we set _{}, we can rearrange this to get

_{},

which is
our Fibonacci Sequence. So if we try the
solution _{}, we get the characteristic equation

_{}

The roots of _{} are _{}. So we have two roots of multiplicity one. This tells us that our general solution is a
linear combination of these roots, or that

_{}

Since we know that _{}, we get

_{}

So if we set _{}, this simplifies correctly, and we have our closed form

_{}

Now,
let's consider the number of ways that we can align dominoes on a _{} checkerboard. Using a _{}, we get two combinations:

If we consider a _{} board, we get the
following three distinct combinations:

Now let's look at the ways we can
combine on a _{}:

Here we get five ways. If we look at a _{} board, we find that we
get 8 possibilities:

We can deduce from this that for
a _{} checkerboard, we get
the Fibonacci number _{}, and we could use the closed form derived earlier to find
the combinations for an arbitrary checkerboard.