Monthly Archives: August 2016

Mathematicians and Computer Scientists

It’s the holiday time of year: so a slightly lazy post for August.  Adapted from a letter published in this month’s edition of Mathematics Today

For anyone who’s worked in the ‘Twilight Zone’ between mathematics and computer science for any time, June’s Mathematics Today article, Urban Maths: A Roundabout Journey [on rounding issues in computer calculations], would have struck a distinct chord.  They will have often come across situations in which mathematicians and computer scientists don’t quite see eye to eye.  The following, fairly well-known, combinatorial exercise is another good example.

How many ordered ways are there of summing contributions of 1 and 2 to a given integer, n?  So, for example, 1+1+2+1+1 and 2+2+2 are two of the 13 different ways of making 6.  Call this number f(n) so that, in this example, f(6) = 13.

The standard combinatorial approach is to consider the first term.  The only two options, 1 (leaving n-1 to make) and 2 (leaving n-2) lead readily to the recurrence relation f(n) = f(n-1) + f(n-2).  Easy enough, yes, but the interesting question now is what to do with it?

Continue reading