Tuesday, February 3, 2009

Another triangular number formula

The double recurrence relation that defines the higher triangular numbers is a simple one - it is no surprise that they turn up so often.

The geometric interpretation is stacking: For a given dimension d, you get the n+1 d-triangular number by stacking the nth d-1 triangular number (the gnomon) onto the nth d-triangular number.  The zero dimensional triangular numbers are just the sequence: 1, 1, 1, 1,..., presumably counting stacks of nothing. The one-dimensional triangular numbers are the naturals: 1, 2, 3, 4, ..., made by stacking the ones of the one-dimensional case. The two dimensional triangular numbers stack the naturals: 1, 3, 6, 10, ..., the three dimensional triangular numbers make pyramids of the triangulars: 1, 4, 10, 20, ....

If you write out a difference table for the higher triangular numbers, you end up with Pascal’s triangle. This suggests a nice formula for the triangulars in terms of binomial coefficients:

From this, you can obtain another recursive formula that you can use when working with higher triangular numbers (this is the “another” formula for this post):

If you vary the defining recurrence relation so that the initial “zero dimensional” value is a number other than 1, you get the other polygonal numbers (square, pentagonal, hexagonal, square-based pyramidal, etc.). In particular, if you let the zero-dimensional value be k-2, you obtain the k-polygonal numbers (k-2 corresponding to the number of triangles in your k-sided polygon).

It turns out there is a nice formula for these in terms of binomial coefficients as well: