Monday, 12 August 2013

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
f_{n-1}^2+ f_n^2= f_{2n}?\label{Square_addition}
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.

No comments:

Post a Comment