Art Benjmain on continued fractions.

This week brings my Art Benjamin related posts to an end. Not only did we discuss Fibonacci sequences, but he also provided me with a lovely interpretation of how continued fractions work and what they represent numerically. His exposition is recounted below.

________________________________________________________________

________________________________________

Here is a typical continued fraction and its simplified form
$$3+\frac{1}{7+\frac{1}{15}}=\frac{333}{106}.$$

Believe it, or not, the numerator and denominator have a combinatorial interpretation. Imagine a strip of squares with one of the numbers in each square (Figure 1).

Figure 1. A strip of three squares containing numbers from the continued fraction. The glass square and the opaque domino.

As with the Fibonacci numbers we want to consider tilings of this strip. This time the square will be made of glass, meaning we can see through it, whereas the domino will be opaque (Figure 1).

As we saw previously there are three ways to tile the board [in Figure 1]. You can tile it with all squares, a domino and a square, or a square and a domino (Figure 2). We’ll say that the weight of the tiling is the product of the numbers that you can see through the glass squares.

Figure 2. All possible weighted tilings of the strip of three numbers using the glass tile and opaque domino.

When you add up all of these tilings you get
$$315+3+15=333,$$
which is the numerator of the fraction.

Now, what about the denominator? Well, clearly the denominator is not influenced by the first number as that is “on top” of the fraction. So, if we ignore the first space and then count the weighted tilings again, we can either have a square and a square, or a single domino (Figure 3). Note that the empty product is counted as one. Adding these together we get 105+1=106, which is the denominator of the fraction.

Figure 3. Weighted tilings after the first number has been eliminated.

So that is a combinatorial way of representing the continued fraction. The top and the bottom are simply counting the weighted tilings. This technique is full generalisable to any length of continued fraction and any numbers you like.

Now suppose I wrote the numbers in reverse so the strip was 15, 7, 3. Notice I haven’t changed the original tilings on this grid so the weighted product will, once again, be 333. This tells you that this continued fraction:

$$3+\frac{1}{7+\frac{1}{15}}$$

will have same numerator as

$$15+\frac{1}{7+\frac{1}{3}},$$

which isn’t obvious from the numbers, but from this visualisation we can immediately spot this.

As above we can finish this calculation by removing the 15 and considering the tiling of a 7, 3 board. The sum of which will be 21+1=22. Thus,

$$15+\frac{1}{7+\frac{1}{3}}=\frac{333}{22},$$

Now isn’t that a fun little way of seeing the fraction?

________________________________________________________________

________________________________________

Over the past few weeks I hope I’ve shown you that Art Benjamin is much more than just a human calculator. His mental arithmetic skills are impressive, but his enthusiasm for mathematics is boundless. I seriously urge you to go see his shows if you get the chance. You will not be disappointed.

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.