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.