The n days of Christmas

A while ago, I read somebody write (probably on Twitter) that the Christmas song The Twelve Days of Christmas is a good way to teach students about quadratic growth, since the time required to sing the song grows quadratically as each verse increases its length. I thought this was great. But the more I thought about it, it started to bother me.

Grammatically, the song is not about what appears to be quadratic growth. In the song, the narrator’s true love gifts them one partridge on the first day, then another partridge in each subsequent day.

On the first day of Christmas, my true love gave to me a partridge in a pear tree.

On the second day of Christmas, my true love gave to me two turtle doves and a partridge in a pear tree.

The narration does not say that the partridge on the second day is the same partridge that was given on the first day. So my interpretation of this is that the narrator, by day two, has now collected two partridges. This changes things.

The question that I’ve been trying to figure out is what the growth rate is for the total number of gifts (where some of these gifts are humans, so that’s weird…) on the nth day of Christmas. Let’s assume for the sake of making the math interesting that the number of days of Christmas grows toward infinity.

They key is that on the ith day of Christmas, a new gift is introduced. This gift will be given in groups of i each day from then on. For example, for i=1, the partridge is introduced, and each subsequent day, the true love gives one more partridge. For i = 2, the turtle doves are introduced, and the true love gives 2 turtle doves each day for the rest of eternity. Another key point is that these gifts don’t start until the ith day.

This pattern means that on the nth day, the narrator owns i(n - i + 1) of the ith gift. That’s a fairly straightforward linear growth. But my main question is how many total gifts does the narrator have on day n?

The formula here is
f(n) = \sum_{i=1}^n i (n - i + 1),
which we can simplify by massaging the equations as follows
f(n) = \sum_{i=1}^n in - \sum_{i=1}^n i^2 + \sum_{i=1}^n i = n \sum_{i=1}^n i - \sum_{i=1}^n i^2 + \sum_{i=1}^n i.

These summations now have some well known formulas. Using the power of my computer science education (and Wikipedia), this formula simplifies to
f(n) = n \frac{n(n+1)}{2} - \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}.
Some more massaging leads to
f(n) = (n + 1) \frac{n(n+1)}{2} - \frac{n(n+1)(2n+1)}{6}.

It’s looking like it’s cubic growth. But let’s finish to make sure. We can combine fractions now, leading to
f(n) = \frac{3n(n + 1)(n+1)}{6} - \frac{n(n+1)(2n+1)}{6} = \frac{3n(n+1)(n+1) - n(n+1)(2n+1)}{6}= \frac{1}{6} (n^3 + 3n^2 + 2n).

Thus, the total number of gifts received by the narrator is \Theta(n^3).

Merry Christmas and Happy Holidays!

This entry was posted in Uncategorized. Bookmark the permalink.

One comment

Leave a comment