Monday 29 July 2013

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

Monday 15 July 2013

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

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.

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.

Monday 1 July 2013

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.