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:

$f_0$	$f_1$	$f_2$	$f_3$	$f_4$	$f_5$	$f_6$	$f_7$	$f_8$	$f_9$	$f_{10}$	…
1	1	2	3	5	8	13	21	34	55	89	…

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$	$1^2+1^2=2$
$f_1^2+ f_2^2= f_4$	$1^2+2^2=5$
$f_2^2+ f_3^2= f_6$	$2^2+3^2=13$
$f_3^2+ f_4^2= f_8$	$3^2+5^2=34$

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

$$t_n=t_{n-1}+t_{n-1},$$

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).