The n days of Christmas

Tom Rivlin

1 December 2016

• Click to share on Twitter (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Reddit (Opens in new window)

This post was part of the Chalkdust 2016 Advent Calendar.

So it’s nearly Christmas, which means it’s time to celebrate one of my favourite maths problems ever. Get some hot cocoa, warm yourself in a blanket by the fireplace, and get ready for the magical tale of the $n$ days of Christmas.

Here’s how it goes: we all know the song. My true love is giving to me an ever-increasing number of gifts over the twelve days of Christmas. If we wanted to sing it, it’d be twelve verses of increasing length. But mathematicians are lazy, so we would sing it not with rhythm, but with algorithm, like this:

This would then be followed by a list of what each of the $a_n$ items were, from partridge in pear tree to drummers drumming.

So, being the well-trained mathematicians I’m sure you all are, hopefully a question should be occurring to you: how many items are given in total over $n$ days?

This is a fascinating question! Think about it, on the first day you are given one item: a partridge in a pear tree (let’s count partridge and pear tree as one item for simplicity). On the second day you are given three items: the partridge in the pear tree, and two turtle doves. So, by the end of day two, you have received four items overall. If the function $T(n)$ is the total sum of all the gifts received by the end of day $n$, then $T(1)=1$, $T(2)=4$… and then what? What’s $T(3)$? $T(12)$?

What’s $T(n)$?

To answer this, we need to think cleverly about how to formulate the problem. Firstly, let’s think about how many gifts are received on a given day. Let’s call this $S(m)$, the sum of all gifts received on day $m$. On each day, it’s going to be the sum of all the integers from $1$ to $m$. So on day $1$, $S(1)=1$. Duh. On day $10$ it’ll be $S(10)=10+9+8+7+6+5+4+3+2$… and a partridge in a pear tree! If you simply add these then you get that $S(10)=55$.

What does this look like in general? Why, a simple summation formula! One of the simplest possible, in fact:

$$S(m) = \sum_{i=1}^{m}i.$$

You just add the counting index to the sum at every iteration!

So let’s explore some of the properties of this function, $S(m)$. First, here’s what WolframAlpha will tell you it is:

$$S(m)=\sum_{i=1}^{m}i = \frac{1}{2}m(m+1). $$

That is, you can prove that the sum of the first $m$ natural numbers is always half $m$ times $(m+1)$. In fact this was first discovered by the ancient Greeks and, according to legend, independently derived by maths superstar Gauss when he was a child.

One of the ways to derive the formula for $S(m)$ is to realise the fact that the sum of the first $m$ natural numbers is always what’s called a triangular number. That is, it’s a number that can always be represented in the following form:

The sum of the first one natural numbers ($m=1$) is just itself: one. Then every new natural number, $m$, adds a row of dots underneath of length $m$, creating a triangle shape. So the $m^{\rm th}$ triangle has $m$ more dots than the triangle before it, so the total number of dots is equal to the sum of the first $m$ natural numbers.

From here we can motivate a geometric proof of the formula for $S(m)$ by combining two such triangles together to create a rectangle:

This rectangle clearly has area $2S(m)$ and sides of length $m$ and $m+1$, meaning the area is $m(m+1)$.

So $2S(m)=m(m+1)$, so $S(m)=\frac{1}{2}m(m+1)$.

So that’s stage one done, but we’re not finished yet.

We now know how many gifts are received on a given day, so the next bit is ‘simple’. We just need to add the $S(m)$s from each day up to day $n$. This is because on day one we receive $S(1)$ gifts, on day two we receive $S(2)$ gifts, and so on, so by day $n$ we have received $S(1)+S(2)+\dots+S(n)$ gifts. In other words, we need to perform the following sum:

$$T(n) = \sum_{m=1}^{n}S(m). $$

That is, do $S(1)+S(2)+\dots$ up to $S(n)$. Of course, $S(m)$ is a sum in and of itself, so $T(n)$ turns out to be a sum of a sum. Sumception.

Now we want a proper analytic expression for $T(n)$, so let’s have a look at it:

$$T(n) = \sum_{m=1}^{n}S(m) = \sum_{m=1}^{n}\left(\sum_{i=1}^{m}i\right) = \sum_{m=1}^{n}\left( \frac{1}{2}m(m+1) \right). $$

And what does WolframAlpha have to say?

$$T(n) = \frac{1}{6}n(n+1)(n+2). $$

That’s nice, but we can do better. Just like the $S(m)$ is the $m^{\rm th}$ triangular number, the $T(n)$ have an interesting property: they are the pyramidal, or tetrahedral numbers. What does that mean? If the triangular numbers make a triangle, then the tetrahedral numbers make, well, a tetrahedron:

The picture clearly shows that each new layer is a bigger triangle put below the layer above it. With each iteration the pyramid gets bigger. The number of balls you’re adding each time is going to be a triangular number, so clearly the tetrahedral numbers are formed from adding the triangular numbers. You can then use a similar geometric proof to the above one for the triangular numbers to obtain the result for $T(n)$ (naturally it’s a bit more complicated). Of course, this is exactly what’s happening in our $n$ days problem: we’re adding successive triangular numbers, so the two problems are identical, and we have our answer: by day $n$ my true love has given to me a sixth of $n$ times $(n+1)$ times $(n+2)$ gifts. That’s a lot of expensive gifts!

Notice how whereas the triangular numbers increased in size quadratically due to the $n^2$ term, the tetrahedral numbers increase in size cubically due to the $n^3$ term. So even for small $n$, the $T(n)$ is quite large. It has everything to do with the fact that numbers are 1D, triangles are 2D and tetrahedra are 3D. In fact, the form of $T(n)$ is almost identical to that of the sum of the first $n$ squares. By summing numbers, you get a quadratic, and by summing that sum you go up a level to cubics—think of it like a multidimensional integral.

What we’ve done here is representative of good mathematics. We’ve seen a problem, equated it to simpler problems we already know the answer to, generalised it to different cases, and given an intuitive feel for why the results are the way they are. Christmas can now last as long as we want it to and we will always have control over the number of presents. The formula can now even be applied to other, similar cumulative counting songs like the Jewish Passover song Echad Mi Yodea, which has thirteen verses!

So, only one question remains: after twelve days of Christmas, how many gifts have been given in total? It turns out, by an amazing coincidence, that $T(12)=364$.

That’s right: over the twelve days of Christmas, my true love has given to me one gift for every day of the year…

…except Christmas Day!

And on that note, MERRY CHRISTMAS TO ALL, AND TO ALL A GOOD NIGHT!

Attributions:

[Pictures: 1 – adapted from Flickr.com – Drummers Drumming by Tom Magliery, CC-BY 2.0;  other pictures by Chalkdust]

Tom Rivlin

Tom is a PhD student in the UCL Physics Department, simulating atomic collisions. He likes to think that what he does ‘technically counts as maths.’

 @TomRivlin   tomrivlin.com    All articles by Tom