Triangular Numbers

I like to imagine that the triangles are equilateral. That's the most beautiful form, I think, but even I have to admit it's not the most practical. So, sometimes you'll want to imagine right triangles instead.

In that representation, it's obvious that you can combine two copies of a triangle to get a square with the diagonal covered twice. In other words, if T(n) is the n^th triangular number, then

T(n) +	T(n) = n2 + n
	T(n) = (1/2) n(n+1).

Another thing that's obvious in that representation is that triangular numbers are just what you need to count symmetric and antisymmetric matrices.

Here are the first few triangular numbers. I learned these a long time ago, and have found them very useful … but I've also never regretted not learning more.

0	0
1	1
2	3
3	6
4	10
5	15
6	21
7	28
8	36
9	45
10	55

And then, if you do need one or two more, it's easy enough to compute them by adding rows … 55 + 11 = 66, 66 + 12 = 78, etc. It's also not hard to apply the general formula from above.

Speaking of adding rows … if you do induction on that, or if you just look at the pretty pictures, you can see one of the reasons triangular numbers are so useful.

T(n) = sum _{k=1 … n} ( k )

I've always been fascinated by the analogues of that equation, starting with the “pyramidal numbers”

P(n) = sum _{k=1 … n} ( k² )

and progressing to sums of k^s for arbitrary s. Here are the factored closed forms of the first few of those. I don't especially like the last two, I'm just including them so you can see that they're not nice.

s		sum
0		n
1	T(n)	(1/2) n(n+1)
2	P(n)	(1/6) n(n+1)(2n+1)
3	Q(n)	(1/4) n2(n+1)2
4		(1/30) n(n+1)(2n+1)(3n2+3n−1)
5		(1/12) n2(n+1)2(2n2+2n−1)

By the way, there's an amazing little fact hidden in there.

Q(n) = [ T(n) ]²

In other words,

sum ( k³ ) = [ sum ( k ) ]².

If there's a geometrical interpretation of that fact, I don't know it. Since each sum and each power of k represents a single dimension, it would be natural for any interpretation to be four-dimensional … but I still can't find one. This is a perfect example of what I was talking about in Some Mathematics.

One pleasant feature of the closed forms listed above is that you can use them to compute sums of arbitrary polynomials. If, for example, you want to know about the “tetrahedral numbers”

H(n) = sum _{k=1 … n} ( T(k) ),

you just proceed as follows.

sum ( T(k) )	= sum ( (1/2) k(k+1) )
	= (1/2) sum ( k2 + k )
	= (1/2) sum ( k2 ) + (1/2) sum ( k )
	= (1/2) P(n) + (1/2) T(n)
	= (1/12) n(n+1)(2n+1) + (1/4) n(n+1)
	= (1/6) n(n+1)(n+2)

Wow, that last line is suggestive, isn't it? There's a whole little theory in there that I never heard of! I won't go into detail, since it's not something I'd intended to talk about, and I'm sure it's already been fully developed elsewhere, but I can't resist giving a quick outline. If you consider functions on the domain of integers, you can define discrete versions of the integral and derivative.

(If)(n) = sum _{k=1 … n} ( f(k) )
(Df)(n) = f(n) − f(n−1)

The combinatorial coefficients (n+(s−1) choose s) play the same role in this system as the functions (1/s!) n^s do in normal calculus, and the first few of them are 1, n, T(n), and H(n).

The last thing I wanted to talk about is a method I invented long ago to compute the (unfactored) closed forms of sums of k^s. I know now that it's not the best method, but I still find it pleasing and interesting.

Let's look at sums of cubes as an example. First, assume that the closed form Q(n) is polynomial over n.

Q(n) = sum ( c_inⁱ )

Then, on the one hand, we have

Q(n+1) − Q(n) = sum ( c_i [ (n+1)ⁱ − nⁱ ] );

on the other hand, we know by definition that

Q(n+1) − Q(n) = (n+1)³.

If we expand the binomials and equate the coefficients of different powers of n, we get a matrix equation for the coefficients of the polynomial Q(n). Here's what that looks like with the answer filled in; note that the binomial coefficients end up reproducing a sizeable chunk of Pascal's triangle.

1	1	1	1		0		1
	2	3	4		1/4		3
		3	6	×	1/2	=	3
			4		1/4		1

And, here are the answers for everything up to sums of twelfth powers.

1

1/2

1/2

1/3

1/2

1/6

1/4

1/2

1/4

0

1/5

1/2

1/3

0

−1/30

1/6

1/2

5/12

0

−1/12

0

1/7

1/2

1/2

0

−1/6

0

1/42

1/8

1/2

7/12

0

−7/24

0

1/12

0

1/9

1/2

2/3

0

−7/15

0

2/9

0

−1/30

1/10

1/2

3/4

0

−7/10

0

1/2

0

−3/20

0

1/11

1/2

5/6

0

−1

0

1

0

−1/2

0

5/66

1/12

1/2

11/12

0

−11/8

0

11/6

0

−11/8

0

5/12

0

1/13

1/2

1

0

−11/6

0

22/7

0

−33/10

0

5/3

0

−691/2730

As it happens, I took these numbers from a program I just wrote, but I know I worked out most of it by hand, once, way back when. I also learned, somehow or other, that the numbers on the diagonal are called Bernoulli numbers; what I didn't learn, or maybe forgot, is that if you know those, the others follow a fairly simple pattern.

The funny thing is, I always thought it was just an accident that the numbers were Bernoulli numbers … I thought the numbers had been discovered in some other context, and then just happened to apply to sums of powers too. But, apparently that was wrong. Bernoulli was investigating the exact same problem, and in fact the closed forms I've been talking about are essentially just Bernoulli polynomials. Those last two links lead to a whole world of theory that I've never run into.