Why do the Fibonacci numbers count these sums and tilings?  Well, let’s look at the tilings.  If we are trying to tile an n-board, by definition, we have
ways of doing this.  For any given tiling, we have to start with either a square or a domino.


If our tiling started with a square, we have
ways of tiling the rest of our board.  If our tiling started with a domino, we have
ways of finishing our tiling.  So we must have that our total number of tilings of an n-board is




This makes it a lot easier for us!  All we need to check is that for a tiling of a 0-board and a 1-board, we have exactly one way of tiling them each.  As a 0-board (a board with no tiles) has only one way to tile it (we can’t do anything,) that one’s easy.  A 1-board on the other hand also only has one tiling - just put down a single square.


So we have exactly the relations which define the Fibonacci numbers, and we can work with these tilings instead.

 




Using the representation of the Fibonacci numbers as these tilings gives us some nice identities very quickly.


For starters, we get a relatively unexpected identity.


Identity 1. 




While this isn’t particularly easy to show using the recursive definition of the Fibonacci numbers, it is very easy to show using this tilings.


Let’s break our board up into the first m squares and the last n squares.  If we’re looking at a particular tiling and we don’t have a domino that sits on the mth square and the (m+1)st square, then we say that our tiling is “splittable” at m.  How many of these do we have for an (m+n)-board?














Note here the first m tiles (purple arrows) and n tiles (red arrows) are splittable at m in the first but unsplittable in the second.


Well, if we have a tiling with no domino across those two spaces, then we must have an m-tiling sitting right next to an n-tiling, so there must be
of these.


If we did have a domino across those two squares, we say that our tiling was “unsplittable.”  What does our tiling look like then?  This time, we’ve got an (m-1)-tiling sitting next to a domino, sitting next to an (n-1)-tiling.  We have exactly
of these, and our tiling had to either be splittable or unsplittable - so our equality follows.


Identity 2.


Another surprising identity is the following:




What does this say?  Well, it says the sum of the first n Fibonacci numbers is the (n+2)nd Fibonacci number minus one.  To show this, we’d like to show that both sides count the same thing.


Right Hand Side.  This counts the number of tilings of an (n+2)-board with squares and dominoes, leaving out the tiling made up entirely of n+2 squares.


Left Hand Side:  Let’s see how this is the same as the right hand side.  Let’s condition on where the last domino goes in.  After the last domino, we will have only squares.  Before the last domino, we can have any tiling - so for a last domino starting at square k+1, we can have any tiling of a k-board before that domino.


Since the last domino could have started anywhere between the first square and the (n+1)st square, we see that we have




tilings of an (n+2)-board that contain a domino.  So we’re done!
















 

Section 1.  1,1,2,3,5,8,13,21...

Section 2.  Some Fibonacci Identities