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.

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

Arthur Benjamin, the man, the maths, the magician. Part 2.

Last week I presented the first half of my interview with Arthur Benjamin, where we discussed his mathematical interests. This week we delve a little more deeply into his entertaining persona.

________________________________________________________________

________________________________________

Is the term mathemagic not a contradiction? Magic implies that there is some trick, whereas maths should be a rigorous science. Moreover, maths should be about sharing ideas, whereas magic is about protecting the secret.

I want my audience to say “How did you do that?” and because it is not strictly magic I feel ok with divulging the mathematical secrets. If I’m presenting at a school you’ll get more excitement from hearing the magician part than the mathematics part. I hope it lives up to its promise that I’m doing maths that feels like magic.

Have you ever had to compromise your academia?

Had I gone to a different university that cared exclusively about research and not about teaching and outreach I think I could have published more. I’ve written about 70 papers, but most of them aren’t frontier breaking or paradigm shifting. I’ve just been lucky to be able to work on problems that I’ve found interesting.

If you had to give one up?

Fortunately, I’ve never had to, which is one of the great perks of being in academia, but [heavy sigh] I suppose I would stay with the academia. The entertainment shows I do are very similar each time. My act hasn't changed much in the last 30 years! I could develop new material, but it might feel repetitious. By doing it occasionally I can maintain my enthusiasm.

What does your family think about it?

They’re used to it [big grin].

What mathematical performers do you rate?

There are more people performing entertaining mathematics in the UK than in the US. I see people here like: Matt Parker, Colin Wright, James Grime, Rob Eastaway, Andrew Jeffrey, Sara Santos and Marcus du Sautoy, who are really out there on the streets. I don’t think the US has anything similar. There are many brilliant teachers in the US, but not so many go on the road with it.

There are people who have linked other ways of entertaining through maths such as: Tim Chartier; who does “Maths and Mime”, Colin Adams; who writes mathematical plays, Larry Lesser; who produces funny maths songs, Ed Burger, who gives funny and profound mathematical talks.

What is your favourite trick?

My favourite part of my show is when I square or multiply large numbers because that is such a personal process. It’s a trick that very few people in the world can perform.

Questions from twitter:

@nnvmath

1) What math concept did he find most difficult to grasp?

I’ve always been more comfortable with maths that used numbers, rather than say geometry. I’m very much a discrete mathematician. I don’t think I knew that until I started graduate school. Mathematics has become much more categorised than it was 30-35 years ago and so it is easier to find what you’re interested in.

2) What math concept is typically the hardest to teach?

Any subject that I don’t know is harder to teach, but that is because I haven’t spent enough time thinking about how to teach them. I don’t know what examples will engage an audience.

@vandichowchow

What makes more sense: pi or tau? Decimal or duodeciamal system?

I’m a big tau lover. I agree with the statement that if we could go back in time and change the factor to tau we would have simplified our theorems and formulas. Obviously, it will be very hard to change people’s perceptions in order to use tau, but maybe in mathematics there is enough of a will to do such a thing. I’ve seen books now that proudly claim “tau certified”.

As for which system, we’re stuck with these ten fingers and although you can use them to count higher using to use base 60, I don’t think we could have used our minds to remember a 60x60 multiplication table.

@TechnicalBen1

Are you excited with the recent progress on twin primes (or any other progress in maths)?

Very excited. It is one of the most accessible and open problems still out there. It is right up there with Fermat’s last theorem. That’s not true with the Riemann hypothesis. It’s exactly like Goldbach’s conjecture, or the four colour theorem, everyone can understand the question and you can even play with the simple cases. I’m also delighted that the recent progress came from a relatively unknown mathematician. Yay for the underdog!

________________________________________________________________

________________________________________

Although the interview is over the mathematics is still not done! Over the next three posts I will be presenting three combinatorial proofs from Art Benjamin on patterns in the Fibonacci sequence as well as how to understand continued fractions.

Arthur Benjamin, the man, the maths, the magician. Part 1.

Recently I got the chance to meet up with Arthur Benjamin, a mental maths extraordinaire. If you’ve never heard of him I urge you to at least go watch his TED talk. His ability to manipulate numbers with speed and skill is astounding. Whilst interviewing Art I found that his enthusiasm for expositing mathematics could not be contained and is extremely infectious. Thus, what follows is a greatly reduced interview. I’ve cut out two large chunks on patterns in the Fibonacci numbers and continued fractions that deserve a whole post to themselves. Moreover, I've split the interview into two halves. This week I try to get to the mathematician behind the mathemagician.

________________________________________________________________

________________________________________

Arthur Benjamin enjoying a sunny Oxford day.

Thank you for allowing to be interviewed for my website. The first question, of course, has to be: how are you doing?

I’m doing well thank you. I’m enjoying my time in Oxford.

What have you been up to on your sabbatical year in Oxford?

I was kept pretty busy here. I gave a TEDX talk in November and a public lecture organised by the University of Oxford’s physics department, which led to a number of schools contacting me.

What are you currently working on research wise?

The main research that I’ve done has been in the area of combinatorics, specifically, finding combinatorial proofs of interesting identities. To take a simple example we know [1] that

\begin{equation}
\sum^n_{k=0}\left(\begin {array}{c} n\\k\end {array}\right)=2^n.
\end{equation}

Now, one can prove that algebraically very easily, but combinatorially you can look at this as an identity where you have a question that gets answered in two ways: how many subsets, 1 through $n$ are there? Well we know there are
\begin{equation}
\left(\begin {array}{c} n\\k\end {array}\right)\nonumber
\end{equation}
subsets of size $k$ and $k$ can run from 1 to $n$, which we can add up, which is the left-hand side of the identity. On the other hand the subsets of can be created in $2^n$ ways because each element is either in or out of the subset.

Each side of the equality tells you something different about the numbers. You can think of it as the same story being told from two different perspectives, which leads to two expressions meaning the same thing.

I assume that, unlike your given example, you do not always know that the identity is true to begin with.

Often you do. It isn’t often that I find brand new identities; rather, I find simpler explanations for known ones. As nothing in mathematics is simpler than counting if you can prove something without heavy algebra or analysis then it is much more satisfying. Sometimes these insights lead to new patterns and identities.

Are your sequences mathematically motivated, or do they stem from a specific application?

To be honest I don’t mind. I just prefer sequences that produce pretty patterns and results.

Which came first maths or magic? And did your love of both lead you on to choosing your route into combinatorics?

If you mean real maths like we’re discussing here then magic certainly came first. If you mean maths as a love of arithmetic then that’s a much harder question as they occurred at a much closer time. I’ve always loved playing with numbers, since I was a kid. I always saw it as a game. I particularly like pulling problems apart and solving them in different ways. 

I’ve always been something of a show off; a ham, as we would say in the US. I grew up in a rather theatrical family, so I’ve always been encouraged to find things that I was passionate about. While I was in High School I would entertain children’s parties with the traditional rabbit out of a hat type of tricks, anything to make them laugh.

As I got older I took an interest in magic of the mind and my dad said,

“Hey, why don’t you do some of that maths stuff in there? What you can do with numbers is much more impressive than the fake mind reading stuff.”

Well, I tried it and, because it is so real, it got the best reaction. That made me think wow! If they like that imagine what would happen if I did bigger problems.

Of course you’re well known for your mental arithmetic abilities, but do you ever entertain people with your research?

If I am talking to a group of mathematical students, then I could talk to them for hours without multiplying any numbers. The general public though are much more interested in the speed mental skills. I’ve always viewed myself as an entertainer; when I’m in the classroom, or when I’m writing my papers, I want them to be enjoyed. That’s not to say that they need to contain corny jokes, just an interesting story.

________________________________________________________________

________________________________________

Part 2 will be up in two weeks.

[1] Now, of course you may not known this identity. An analytic proof can be found here. However, the mathematics is not the point of interest here. It is simply that each side of the equality means something different.

Facing the Challenge of the Puzzle Museum.

Mathematics has the reputation of being an esoteric science wrapped up in theoretical objects that have no place in the physical world. But what is mathematics if not a huge elaborate game? You lay down your rules (axioms) at the start, set up your pieces (algebraic structure) and follow the game until you reach the end (solve your problem).

With this in mind Alain Goriely, Jon Chapman, Derek Moulton, Thomas Lessinnes and myself journeyed all the way to Devon to meet the wonderful James Dalgety, curator of the world’s biggest collection of puzzles and related ephemera. Our goal was to discover pieces amongst James’ 50,000+ puzzles that highlighted and demonstrated key mathematical ideas in a physical manner and, thus, could be used to form the basis of a puzzle exhibition in honour of the opening of the new University of Oxford Mathematical Institute.

Figure 1. James (centre) presenting just a small fraction of his entire collection to admiring crowd of (left to right) Derek, Alain, Jon and Thomas.

James’ tour through his house-cum-gallery took over four hours and spanned three large rooms, which were filled to bursting point with every conceivable puzzle type. Simply put, we were kids in a candy shop! Although we saw a great number of puzzles and even had a chance to try out our problem solving abilities, we hardly scratched the surface of his entire collection as beneath every full cabinet was a set of drawers, each carefully sorted and catalogued to contain a specific type of puzzle. Even within each category of puzzle James would have a number of examples, ranging from updated versions fresh from a 3D printer to originals, which entertained troops in first world war trenches. Indeed, the collection is of much an historical and anthropological interest as it would be to any puzzle enthusiast.

Throughout the day James provided a constant conveyor belt of entertaining puzzles for us to try. Although at this stage it is important to note that one of James’ house rules is: if you dismantle a puzzle then you cannot leave until it is solved. Personally, I am happy to say that we did Oxford proud and rose to the challenge. Working together (and with the odd nudge in the right direction from James) we were a match for any challenge. Alain and Thomas even managed to offer a solution to one of James’ previously unsolved French rebus plates.

Figure 2. Left: Derek supervising Jon and Alain as they try and untangle a knotty situation. Right: (left to right) Thomas, Alain, Jon and Derek all engrossed in puzzle heaven (or hell depending on your view).

By 7pm we felt we had encroached upon James’ hospitality enough, knowing full well that it would be another three hours before we got back to Oxford. We said our goodbyes, signed the guest book and set off with grins on our faces and a long list of mathematical puzzles that would make perfect exhibits for the new institute. 

Although it was the end of the day our work had just begun. We now have to refine our ideas and consider the specifics of the exhibition. Not only do we want James’ puzzles to be the centerpiece but we also need to create accompanying texts and explanations to show how the maths and the puzzles fit together. But that is a story for another day.

Egg shells to turtle shells.

Over the past few weeks we have looked into the production of self righting objects. We started by considering weebles that have heavy bottoms, we then took a detour and looked at the stability of egg shapes and how we could make any shape have more stable points. Finally, we saw the work of Gábor Domokos and Péter Várkonyi and their discovery of the gömböc.

No matter how you initially orient the gömböc it will always wobble and rotate itself to finish standing upright. Importantly, the gömböc is made of only one material, so its density is uniform. Mathematically, the gömböc is known as a mono-monostatic body. This simply means that it has exactly one stable and one unstable equilibrium point.

Figure 1. A procelain gömböc. Hand painted by Ms. Pálma Babos [1].

This is all very nice and the gömböc makes a beautiful little toy to play with, but is it useful for anything other than a paper weight? Amazingly the answer appears to be yes. Embarrassingly, nature had solved the problem a long time ago in the form of the turtle shell.

Many turtles have quite flat shells and use their necks to turn themselves over using a so named “break dance” technique as seen in Figure 2. However, for turtles with much taller shells this is not possible because their neck is not long enough. Thus, a couple of turtle species have shells shaped like a gömböc in order to allow them to roll over easily. The movie below shows Gábor actually putting some turtles on their back and watching them right themselves.

Figure 2. Self righting turtles. On the left a relatively flat turtle uses its neck. On the right, the turtle uses a gömböc shaped shell.

Figure 3. As the shell gets higher relative to its width the number of equilibria change.

Perhaps the most impressive link between the mathematics of the gömböc and the turtle shells is that alterations of the gömböc shape can be linked to different species. Importantly, as the gömböc height is varied the number of stable and unstable equilibria change. This is also seen on the shells. This is shown in the Figure 3.

So what have we learned over the last few weeks? For me, it is good maths will always lead to interesting outcomes and that nature is a far better mathematician that we will ever know.

For more information on gömböcs and their connection to turtles take a look at www.gomboc.eu or the original research paper can be found here.

________________________________________________________________

________________________________________

[1] The Herend porcelain gömböc is a high-end, beautiful piece of art but, sadly, it does not work. Porcelain technology is simply not good enough. Picture taken from http://www.gomboc-shop.com/

Self righting turtle photos courtesy of Gábor Domokos and Timea Szabó.

Video taken from http://plus.maths.org/content/story-goumlmboumlc

Turtles:

http://www.petinfoclub.com/Images/pancake%20tortoise%20shutterstock_32509753-1.jpg

http://www.flickr.com/photos/jackol/133765382/sizes/l/in/photostream/

http://www.flickr.com/photos/40295335@N00/3304210776/sizes/o/in/photostream/