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?
