Tetrahedral number formula

Start with the sequence of positive integers:

1, 2, 3, 4, …

Now take partial sums, the nth term of the new series being the sum of the first n terms of the previous series. This gives us the triangular numbers, so called because they count the number of coins at each level of a triangular arrangement:

1, 3, 6, 10, …

If we repeat this again we get the tetrahedral numbers, the number of balls on each level of a tetrahedral stack of balls.

1, 4, 10, 20, …

We can repeat this process and general define T_{n, d}, the nth tetrahedral number of dimension d, recursively. We define T_{n, 1} = n and for d > 1,

$T(n, d) = \sum_{i=1}^n T(i, d-1)$

This is just a formalization of the discussion above.

It turns out there’s a simple expression for tetrahedral number of all dimensions:

$T(n, d) = \binom{n+d-1}{d}$

Here’s a quick proof by induction. The theorem clearly holds when n = 1 or d = 1. Now assume it hold for all n < m and d < m.

$\begin{eqnarray*} T(n, m) &=& \sum_{i=1}^n T(n, m-1) \\ &=& T(n, m-1) + \sum_{i=1}^{n-1} T(n, m-1) \\ &=& T(n, m-1) + T(n-1, m) \\ &=& \binom{n+m-2}{m-1} + \binom{n+m-2}{m} \\ &=& \binom{n+m-1}{m} \end{eqnarray*}$

The last line follows from the binomial addition identity

$\binom{a}{b} = \binom{a-1}{b} + \binom{a-1}{b-1}$

It also turns out that T_{n, d} is the number of ways to select d things from a set of n with replacement.

Tetrahedral numbers

Similar posts

5 thoughts on “Tetrahedral numbers”