Monday, 29 July 2013

Art Benjamin on Fibonacci patterns.

Whilst interviewing Art Benjamin, I found that he could not help highlighting simple and intuitive results from the Fibonacci sequence. I extracted them from the original interview to ensure that they got a treatment that they deserve. If you like these he has written a book called “Proofs That Really Count”, co-authored with Jennifer Quinn. The book contains dozens of mathematical identities, which are proven combinatorially.

This week Art gives us the basics of the Fibonacci numbers.
 Let’s take the Fibonacci numbers:

Now, there are all kinds of fun little patterns within these numbers, for example: if you square and add consecutive Fibonacci numbers you get the even Fibonacci numbers,

$f_0^2+ f_1^2= f_2$
$f_1^2+ f_2^2= f_4$
$f_2^2+ f_3^2= f_6$
$f_3^2+ f_4^2= f_8$
Well, why is that? If you had a formula for the $n^{th}$ Fibonacci number, maybe using square root of five and the golden ratio, you could use algebra to prove that
$$f_{n-1}^2+ f_n^2= f_{2n}.$$
But if we know what these numbers are counting then you will be able to see this identity in a more direct way.

Before we do prove the above formula we need to know a little more about the Fibonacci numbers. What do they count? Consider a strip of $n$ squares. How many ways are there to tile this strip using single squares and dominoes, which are two squares wide (Figure 1).
Figure 1. A strip of $n$ squares are to be tiled using only a single square tile, or a double tile, known as a domino.
I claim that the number of tilings is the $n^{th}$ Fibonacci number. It is easy to check the first few cases. A strip of no squares uses no tiles and this is the only unique tiling. Similarly, a strip of one square can only be covered by a square tile and a two square strip can either be covered with two squares, or one domino, so it has two different tilings. With a strip of three squares it is either: three squares, square-domino, or domino-square, giving three tilings (Figure 2).
Figure 2. (a) Two possible ways of tiling a strip of two squares. (b) Three possible ways of tiling a strip of three squares.

Now consider all the tiling of strip of $n$ squares. Either the strip ends with a square tile, or a domino tile. How many tilings end in a square tile? Well, this is just the tilings of the $n-1$ strip, plus the final square. Similarly, how many end in a domino? This is just the tilings of the $n-2$ strip, plus the final domino. So the total number of tilings of a strip of length $n$ is the number of tilings of the $n-1$ strip, plus the number of tilings of the $n-2$ strip. If we call the number of tiling of the $n$ strip $t_n$ then
so it satisfies the same recursion formula as the Fibonacci sequence. I now claim that any pattern that you can find within the Fibonacci sequence has a similar, simple, maybe clever, combinatorial proof.

Next time Art will use similar techniques to show us how to prove the original identity (1).

No comments:

Post a Comment