Wednesday, October 7, 2009

Three number triangles, two telescoping series

There are so many relations present [in Pascal's triangle] that when someone finds a new identity, there aren't many people who get excited about it anymore, except the discoverer! - Donald E. Knuth (as quoted by Martin Gardner)

I was inspired by a post on Pat's Blog and by reading A.W.F. Edwards's Pascal's Arithmetical Triangle to look at summing the reciprocals of higher dimensional triangular numbers. It turns out that you can use the same telescoping series technique that allows you to sum the reciprocals of the 2-dimensional (i.e. the usual) triangular numbers, and that the 'telescoping' feature of these sums can be expressed in terms of some nice identities.

The statement of the sum is a nice one. For d > 1 we have:

\[\sum^{\infty}_{n=1} \frac{1}{t^d_n} = \frac{d}{d-1}. \]
Which gives you a result of 2 for d = 2 as mentioned in Pat's post. In the case where d = 0 or 1, the series does not converge.

In the notes below, none of the identities are new (the newest is, I think, about 400 years old) - the famous quote by Donald Knuth at the top of the post is intended as a caution for anyone who gets carried away and derives scads more.

In all the statements in this post, the index d ranges over the nonnegative integers (0, 1, 2, ...) while n ranges over the natural numbers (1, 2, 3, ...). This may seem somewhat inconsistent, but we like to start with dimension zero (d = 0) and with the first triangular number (n = 1).

The d-triangular numbers, $t^d_n$ (d for "dimension") are defined by $t^0_n = 1$, and

\[ t^d_n =\sum^{n}_{i=1}t^{d-1}_i \mbox{ for } d > 0. \]

The formula for $t^d_n$ can also be expressed as a difference, $ t^d_n - t^d_{n-1} = t^{d-1}_n $.

When d = 2 we get the usual triangular numbers, d = 3 gives the pyramidals, and d = 4 gives the triangulo-triangulars, etc. - each dimension up is visualized as a stacking of those below it. Note that this definition has the first triangular number (for all dimensions d) as 1 and not 0, as is sometimes preferred; in this context it makes sense to start at 1.

From this definition, and the Pascal identity, you can establish that

\[ t^d_n = \left( \begin{array}{c}n+d-1 \\d \end{array} \right). \]
If you are familiar with Pascal's Triangle and look carefully at the triangular number definition, you'll see that sum in the definition of the d-triangular numbers is the Pascal Triangle "hockey stick theorem" in disguise. This provides us with a direct formula for the d-triangular numbers:

\[ t^d_n = \frac{n(n+1)\cdots (n+d-1)}{d!}. \]
And this also suggests that we arrange the d-triangular numbers into Pascal's triangle, while remembering that we are not indexing them in the way we usually do for the binomial coefficients.

The formula also gives us the opportunity to generate a bunch of identities, like:

\[t^d_n = \frac{(n+d-1)}{d} t^{d-1}_n, \]
\[t^d_n = \frac{n}{d} t^{d-1}_{n+1}. \]
From here we flip each entry in the triangle to obtain a new triangle, the Leibniz triangle (so called by Edwards), whose entries are the reciprocals of d-triangular numbers.

There is a nice difference relationship in this triangle too, for > 1,

\[\frac{1}{t^d_n} = \frac{d}{d-1} \left( \frac{1}{t^{d-1}_n} -\frac{1}{t^{d-1}_{n+1}} \right) \]
To prove this identity, generalize the method that allows you to split up the fraction $\frac{1}{n(n+1)}$ into $\frac{1}{n} - \frac{1}{n+1}$ in the usual telescoping series example.

To get our last number triangle, we divide each entry in the Leibniz Triangle by $(n+d)$, which gives us the Leibniz Harmonic Triangle. In other words, we define $h^d_n = \left(\frac{1}{n+d}\right)\frac{1}{t^d_n}$, and create a new triangle with entries $h^d_n$.

Going back to the formula for $t^d_n$ we can obtain some other identities, like:

\[ h^d_n = \left( \frac{1}{d+1}\right) \frac{1}{t^{d+1}_n}, \]
\[ h^d_n = \left( \frac{1}{n}\right) \frac{1}{t^{d}_{n+1}}. \]
And, as with the other triangles, there is a nice difference relationship, for d < 0 :

\[ h^d_n = h^{d-1}_n -h^{d-1}_{n+1} . \]
This can be proved following the same ideas as was used to show the difference relationship for the inverse triangulars. It's worth contrasting this identity with the corresponding identity for Pascal's Triangle.

Now, if you've proved these identities, there are two easy ways to find the sum, $\sum^{\infty}_{n=1} \frac{1}{t^d_n}$.

First method: use the Leibniz Harmonic triangle.
Taking advantage of these two identities:

\[ h^d_n = \left( \frac{1}{d+1}\right) \frac{1}{t^{d+1}_n}, \]
\[ h^d_n = h^{d-1}_n -h^{d-1}_{n+1} . \]
We can combine them and observe that for d > 1:

\[\begin{array}{lll} \sum^{\infty}_{n=1} \frac{1}{t^d_n} &=& d\sum^{\infty}_{n=1} h^{d-1}_n \\ &=& d\sum^{\infty}_{n=1}\left( h^{d-2}_n - h^{d-2}_{n+1} \right) \\ &=& d\left(\sum^{\infty}_{n=1} h^{d-2}_n -\sum^{\infty}_{n=1} h^{d-2}_{n+1} \right)\\ &=& d\left(\sum^{\infty}_{n=1} h^{d-2}_n -\sum^{\infty}_{n=2} h^{d-2}_{n} \right)\\ &=& d\left(\sum^{\infty}_{n=1} h^{d-2}_n -\sum^{\infty}_{n=1} h^{d-2}_{n} + h^{d-2}_{1} \right)\\&=& dh^{d-2}_{1} \\ &=& d\left( \frac{1}{d-1}\right)\\ &=& \frac{d}{d-1}\end{array}\]

Incidentally, we also have $\sum^{\infty}_{n=1} h^d_n = \frac{1}{d}$ for d > 0.

Second method: use the reciprocal difference identity for the Leibniz triangle.
Here we see that everything comes directly from the identity:

\[\frac{1}{t^d_n} = \frac{d}{d-1} \left( \frac{1}{t^{d-1}_n} -\frac{1}{t^{d-1}_{n+1}} \right). \]
We have, for d > 1:
\[\begin{array}{lll} \sum^{\infty}_{n=1} \frac{1}{t^d_n} &=& \frac{d}{d-1}\sum^{\infty}_{n=1} \left(\frac{1}{t^{d-1}_n} - \frac{1}{t^{d-1}_{n+1}}\right)\\&=& \frac{d}{d-1}\left(\sum^{\infty}_{n=1} \frac{1}{t^{d-1}_n} - \sum^{\infty}_{n=1}\frac{1}{t^{d-1}_{n+1}}\right)\\ &=& \frac{d}{d-1}\left(\sum^{\infty}_{n=1} \frac{1}{t^{d-1}_n} - \sum^{\infty}_{n=2}\frac{1}{t^{d-1}_{n}}\right)\\ &=& \frac{d}{d-1}\left(\sum^{\infty}_{n=1} \frac{1}{t^{d-1}_n} - \sum^{\infty}_{n=1}\frac{1}{t^{d-1}_{n}} + \frac{1}{t^{d-1}_{1}} \right)\\ &=& \frac{d}{d-1}\left(\frac{1}{t^{d-1}_{1}}\right) \\ &=& \frac{d}{d-1}\end{array}\]

After working out all this, I came across the same "reciprocal of generalized triangular numbers" problem at Topological Musings - solution #3 is the same as the one here, but expressed in terms of binomial coefficients (and without extracting some general identities among the terms).