At trivia the other night, my family got this question:
In the “12 days of Christmas” song, how may total gifts does the singer receive?
In the song, the singer gets 1 gift, then the next day they get two gifts plus the gift they got on the first day again, then they get three gifts plus all the gifts they got on the second day, and so on. So the answer to the trivia question is 364, which we could trivially compute in Python as:
sum([x*(x+1)/2 for x in range(1,13)])
But the fun math question is obviously, can we find a closed form for the total for any number of days $n$?
The obvious first thing to think of is Gauss’ trick, which I of course already used in my Python code above. This trick is usually presented as “Gauss noticed that the sum of eg all numbers from 1 to 100 could be broken into pairs that add to 101 (1+100, 2+99, etc),” but there’s another way to conceptualize it! Maybe a more… geometric way?
Thinking geometrically, we might understand Gauss’ trick as the discrete version of the integral of the line $x = y$. If a discrete function is defined over the integers, then its ‘derivative’ would just be its first difference: $\Delta f[k] = f[k+1] - f[k]$. Integration is just a sum. We can also see that the fundamental theorem of calculus still works: $\sum_{k=a}^{b-1} \Delta f[k] = f[b] - f[a]$ (the sum telescopes and all but the outer terms cancel).
Let’s try to rederive Gauss’ trick using discrete calculus before we move on to extending it. Gauss’ trick already tells us that we can’t use our memorized integration rules to directly compute a sum: the integral of $f(x) = x$ is $F(x) = 1/2 x^2$, not $1/2 (x^2 + x)$. So we’ll take a slightly more roundabout technique.
We should expect that the integral of a linear function would be quadratic, so let’s set $f[k] = k^2$ for now. That means that $\Delta f[k] = (k+1)^2 - k^2 = 2k + 1$. The fundamental theorem of calculus allows us to set up a cool relationship here, between the original function (on the left - integrating the derivative just gives us the function back, more or less) and the integral of a simplified version of its derivative (on the right).
$$ \begin{align} \sum_{k=1}^n \left( (k+1)^2 - k^2 \right) &= \sum_{k=1}^n 2k + 1 \\ (n + 1)^2 - 1 &= \sum_{k=1}^n 2k + \sum_{k=1}^n 1 \\ &= 2 \sum_{k=1}^n k + n \\ \frac{{(n + 1)^2 - 1 - n}}{2} &= \sum_{k=1}^n k \end{align} $$ This is equivalent to the Gauss formulation! So far this seems like we’ve worked a lot harder than Gauss for not much payoff. But now we get to apply the same trick to sum a quadratic. We should expect the integral of a quadratic to be a cubic:
$$ \begin{align} \ f[k] = k^3, \Delta f[k] = (k+1)^3 - k^3 &= 3k^2 + 3k + 1 \\ \sum_{k=1}^n \Delta f[k] = \sum_{k=1}^n \left( (k+1)^3 - k^3 \right) &= \sum_{k=1}^n 3k^2 + 3k + 1 \\ (n + 1)^3 - 1 &= \sum_{k=1}^n 3k^2 + \sum_{k=1}^n 3k + \sum_{k=1}^n 1 \\ &= 3 \sum_{k=1}^n k^2 + 3\left( \frac{{n (n+1)}}{2} \right) + n \\ {(n + 1)^3} - 1 - \frac{3}{2} n(n+1) - n &= 3 \sum_{k=1}^n k^2 \\ n^3 + 3n^2 + 3n + 1 - 1 - \frac{3}{2}n^2 - \frac{5}{2} n &= \\ n^3 + \frac{3}{2}n^2 + \frac{1}{2} n &= \\ \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6}n &= \sum_{k=1}^n k^2 \end{align} $$
Having derived the sum of the quadratic function, we can return to our naive formulation:
$$\begin{align} \text{total gifts} = \sum_{k=1}^n k(k+1)/2 &= \frac{1}{2} \left(\sum_{k=1}^n k^2 + \sum_{k=1}^n k \right) \\ &= \frac{1}{6} n^3 + \frac{1}{4}n^2 + \frac{1}{12}n + \frac{1}{4}n(n+1) \end{align}$$
In trivia, however, I tried to add up all the numbers manually, forgot to carry a ten, and gave a solution of 354 :’)