Math Explorers Club

Math Explorers Club
Many of you have seen this sequence before - the Fibonacci numbers! The sequence is defined by the following relations and initial terms:
While this sequence does count a number of different things, one of the easiest to work with is the number of ways of summing 1 and 2 to n.
What do we mean by this? Well, consider the following. For n=4, we see that there are five different ways of adding 1s and 2s to get to 4. Let’s look at them:
We can represent this pictorially with tilings of a board with n squares, covered with squares (yellow) and dominos (blue) as below:
Lesson 3: Fibonacci Numbers
Tuesday, July 8, 2008
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.
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