Art Benjamin on Fibonacci patterns part 2.

Last time we had a closer look at the Fibonacci numbers. Although Fibonacci justified them through rabbit breeding we saw that they could also arise from a tiling problem. This week Art expands on the original problem he stated:

how do we show

\begin{equation}
f_{n-1}^2+ f_n^2= f_{2n}?\label{Square_addition}
\end{equation}

________________________________________________________________

________________________________________

Let’s look at the square addition identity (1). What does this say? Suppose we have a strip of length $2n$. How many tilings are there? Firstly, by definition, $f_{2n}$. Secondly, a tiling of length $2n$ can be created by breaking the original strip into two halves. How many ways can I tile this broken strip? Well there are $f_n$ ways to tile each half and, so, the number of ways would be $f_n^2$ (Figure 1(a)).

Now, this is not all the tilings of the $2n$ strip though, because it could happen that we can’t split the strip like this because a domino is placed in the middle. Subtracting this domino means that we now have two strips of $n-1$ squares to tile, giving $f_{n-1}^2$ tilings (Figure 1(b)).

Figure 1. Dissecting a strip of length $2n$ into (a) two length $n$ strips, or (b) two length $n-1$ strips and a central domino.

So, of all the tilings of a $2n$ strip $f_n^2$ do not have a domino crossing the middle section and $f_{n-1}^2$ do have a domino crossing the middle section therefore the total is

\begin{equation}f_{n-1}^2+ f_n^2= f_{2n}.\end{equation}

We’ve taken a question and we’ve answered it in two different ways therefore those answers must be the same.

Inductively, the sum of consecutive Fibonacci squares is difficult to prove without proving a much stronger result by induction, from which the formula (1) will be a specific case. To see the more general result consider the following: originally, I broke the strip in half, but there is nothing special about the centre. Suppose I broke a given strip into two pieces. One of length $n$ and one of length $m$, so the length of the whole strip is $n+m$. By definition, the number of ways of tiling this strip is $f_{n+m}$.

Figure 2. Dissecting a strip of length $n+m$ into (a) a strip of length $n$ and a strip of length $m$, or (b) a length $n-1$ strip and length $m-1$, plus a connecting domino.

How many ways can I tile each of these sections? As before there are $f_n\times f_m$ ways (Figure 2(a)). However, this does not consider the possibility that there is a domino crossing the $n$ and $m$ length sections. As before we can remove this domino leaving strips of length $n-1$ and $m-1$ meaning that there are $f_{n-1}\times f_{m-1}$ ways of tiling these two parts (Figure 2(b)). Putting these both together we generate the stronger result,

\begin{equation}f_{n-1}f_{m-1}+ f_n f_m= f_{m+n},\end{equation}

which is the easier result to prove by induction. If $n$ is 1 the result is trivial and then if you induct on $n$ it will be ok, but who needs induction? These pictures tell you what is happening in general.

________________________________________________________________

________________________________________

Next time Art changes topic and gives us an explanation of what continued fractions actually mean. Interestingly, it is still based on this idea of tiling a strip.

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