A Closed Form for the Fibonacci Sequence

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.