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.