And now, the triumphant termination to the tantalizing tale of tetrahedral totals!
To sum up so far: we began by observing that the number of gifts in the popular song The Twelve Days of Christmas can be described by tetrahedral numbers. Unsatisfied with adding up tetrahedral numbers by hand, we first experimented with using a computer to calculate them for us, but found even that method had its limits. In search of the way of cunning rather than force, we first developed a formula for calculating the simpler triangular numbers, then made a seemingly unrelated detour to discuss binomial coefficients, and saw an amazing connection between binomial coefficients and Pascal’s triangle. It might not be obvious, but we’re incredibly close to our goal — the pieces are in place; all that remains is to put them together.
The first thing to clear up is why on earth binomial coefficients have anything to do with Pascal’s triangle. Remember, the binomial coefficient
tells us how many ways there are to choose k things out of n. As we saw last time, if we make a table of binomial coefficients (with n down the side and k along the top), it is exactly the same as Pascal’s triangle, which is formed by a simple rule of addition: to get each new entry in the table, add the entry above it and the one above and to the left.
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
It’s clear why the left and right sides of Pascal’s triangle are made of all 1′s, and it’s clear why the corresponding binomial coefficients are also equal to 1 (they are of the form or — there’s only one way to choose nothing, or everything). So the real question is, why do binomial coefficients obey the same kind of simple addition rule that creates Pascal’s triangle?
Let’s translate the addition rule of Pascal’s triangle into the language of binomial coefficients. The addition rule says that to get any entry in Pascal’s triangle, you add the entry above it and the one above and to the left; if a particular entry is given by , then the ones above it and above and to the left are and respectively. So the addition rule says that
Why is this true? There’s actually a simple explanation. Suppose you want to choose k things out of n total things. Take the last of the n things and call it Thing Z. (Z for Zucchini. Yes, zucchini is a fruit.) Clearly, you have exactly two choices when it comes to Thing Z: you can include Thing Z in the k Chosen Things, or not. If you don’t include it, then you still have to choose k things, but now you only have n-1 total things to choose from, so you have ways to do it. On the other hand, if you do include Thing Z, then you only have to choose k-1 things from the remaining n-1 to complete your selection; there are ways to do that. Since these are the only two possibilities, and they obviously don’t overlap, the binomial addition identity is born! Neato! [You can also prove this identity by resorting to the definition of binomial coefficients in terms of factorials; a little massaging of denominators, a little factoring, and hey presto! I'll leave that as an exercise for the interested reader.]
Cool, now we know why Pascal’s triangle is just binomial coefficients in disguise (or vice versa). But what does all of this have to do with tetrahedral numbers? Well, do you remember what the first few tetrahedral numbers are? Let’s see… the first few triangular numbers are 1, 3, 6, 10, 15, 21… which would make the first few tetrahedral numbers 1, 4, 10, 20, 35, 56… right? Now go back and stare at Pascal’s triangle.
Do you see it?! We can just read off the tetrahedral numbers from the third column of Pascal’s triangle! (Remember, the leftmost column is the zeroth column.) For that matter, the triangular numbers are in the second column. (And yes, the fourth column is the pentatope numbers, a pentatope being the four-dimensional analog of a tetrahedron; pentatope numbers are created from sums of tetrahedral numbers. And the fifth column is…) It’s not too hard to see why this is so: think about the addition rule, and the progression from a column of all 1′s, to a column of the counting numbers, to a column of triangular numbers, to a column of tetrahedral numbers… (if you have trouble figuring out why this works, leave a comment and I’ll explain in more detail).
So the tetrahedral numbers are just the numbers in the third column of Pascal’s triangle. But here’s the punchline: we already know how to compute the entries of Pascal’s triangle, using binomial coefficients! A moment’s thought reveals that the nth tetrahedral number can in fact be given by (the “+ 2″ is because the first tetrahedral number is actually found in the third row). We can expand this a bit if we want:
Woohoo! Let’s try it:
It works! If you try calculating you’ll get just like we found before. And I’ll leave the fun of calculating to you!