## Monday, 26 August 2013

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