The "N Days of Christmas" Solution

A few days ago in The "N Days of Christmas" Puzzle I asked if you could figure out how many gifts you receive in total for all twelve days (not just on the twelfth day) of the song "The Twelve Days of Christmas," and to find an elegant way to calculate the number of gifts you'd receive if the number of days is extended beyond twelve.

First we need to figure out how many gifts we receive on a given day. It is a cumulative song, so you receive one partridge in a pear tree on the first day, then on the second day you receive two turtle doves and another partridge in a pear tree, and so on for twelve days. So the sequence for each day is:

1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15
...

That's probably enough terms that you'll start to recognize a pattern is forming. Each number in the sequence is just the sum of the first n integers, which you may recognize as the triangle numbers. For a small number of days like 12 we can just continue adding terms to the sequence and have the answer in about a minute. We could look up the formula for the nth triangle number, but with a little bit of intuition we can come up with one ourselves. (When you write your own blog, you get to pretend you're a little bit smarter and less lazy than you really are.) Sometimes it helps to draw a picture like the following:



Notice that the circles form the same sequence that we're after. Also note that since the circles are arranged in a triangle we can calculate the total number of circles by multiplying the height of the enclosing rectangle (n) by the width (n + 1) and dividing by 2. This gives us the formula for the nth triangle number.

$T_n = \frac{n(n + 1)}{2}$

That only gives us the number of gifts on the last day though. We wanted to know the number of gifts on all days combined, and we wanted to know it for any number of days. So what we really want isn't the nth triangle number (the sum of the first n integers), but the sum of the first n triangle numbers. That's a formula that we can derive from what we already know.

$\sum_{k=1}^{n}\frac{k(k + 1)}{2}$

$\frac{1}{2}\sum_{k=1}^{n}k(k + 1)$

$\frac{1}{2}\sum_{k=1}^{n}(k^2 + k)$

$\frac{1}{2}\sum_{k=1}^{n}k^2 + \frac{1}{2}\sum_{k=1}^{n}k$

At this point we should take a moment to say out loud what the two terms in this equation mean in plain English. On the left we have one-half of the sum of the first n squares, and on the right we have one-half of the sum of the first n integers. We already found a formula for the sum of the first n integers, and it seems like there ought to be a similar formula for the sum of the first n squares. There is, and to save us some time I’ll just substitute it here¹.

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

$\frac{(n^2 + n)(2n + 1)}{12} + \frac{n(n + 1)}{4}$

$\frac{(2n^3 + 3n^2 + n)}{12} + \frac{(n^2 + n)}{4}$

$\frac{(2n^3 + 3n^2 + n)}{12} + \frac{(3n^2 + 3n)}{12}$

$\frac{(2n^3 + 6n^2 + 4n)}{12}$

$\frac{(n^3 + 3n^2 + 2n)}{6}$

$\frac{n(n^2 + 3n + 2)}{6}$

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

That gives us our formula for the sum of the first n triangle numbers, which is also known as a tetrahedral number. This is the number you get when you turn the first n triangles on their side and stack them in a pyramid.

So if we plug 12 into the formula above, we find out that in total there are

$\frac{12 \times 13 \times 14}{6} = 364$

total gifts given in the Twelve Days of Christmas.

Happy Holidays!

---

¹ The sequence given by the sum of the first N squares is called the square pyramidal numbers.