How many gifts are there in the song Twelve Days of Christmas?
Day 1: 1 gift
Day 2: 1 + 2 = 3 gifts
Day 3: 1 + 2 + 3 = 6 gifts
Day 12: 1 + 2 + 3 + … + 12 = 78 gifts
The number of gifts on day n is the nth triangular number. The total number of gifts up to and including day n is the sum of the first n triangular numbers, known as the nth tetrahedral number. In the image below, the total number of balls is the fifth tetrahedral number. The number of balls in each layer are triangular numbers. (Image credit: Math is Fun.)
I’ll develop a formula for tetrahedral numbers and continuations of the pattern such as the sum of tetrahedral numbers etc.
First, let T(n, 1) = n.
Next, let T(n, 2) be the nth triangular number. So T(n, 2) is the sum of the first n terms in the sequence T(i, 1).
Next, let T(n, 3) be the nth tetrahedral number. So T(n, 3) is the sum of the first n terms in the sequence T(i, 2).
In general, define T(n, k) to be the sum of the first n terms in the sequence T(i, k-1). You could think of T(n, k) as the nth k-dimensional triangular number. (A tetrahedron is a sort of 3-dimensional triangle. It’s a pyramid whose base is a triangle. T(n,4) would count balls arranged in a sort of 4-dimensional triangle, a simplex in 4 dimensions.)
Theorem: T(n, k) = n(n+1)(n+2) … (n+k-1)/k!
Corollary: There are T(12, 3) = 12*13*14/6 = 364 gifts in the Twelve Days of Christmas.
See these notes for a elementary proof by induction.
Update: Here’s more advanced proof that uses calculus of finite differences. The more advanced proof requires more background, but it also gives a better idea of how someone might have discovered the formula.