<![CDATA[Triangular Numbers]]>

<![CDATA[Triangular Numbers]]>This post is just for fun. I’ll start with Pascal’s triangle and show you the number e hiding inside it. Using this, we’ll see how the product of all numbers in the nth row of Pascal’s triangle is related to the nth triangular number.

That’s cute, because Pascal’s triangle looks so… triangular!

But then, with a massive amount of help from Greg Egan, we’ll dig a lot deeper, and meet strange things like superfactorials, the magic properties of the number 1/12, and the Glaisher–Kinkelin constant.

First let’s get warmed up.

Warmup

Pascal’s triangle is a famous and much-studied thing. It was discovered long before Pascal. It looks like this:

We write 1’s down the edges. We get every other number in the triangle by adding the two numbers above it to its left and right. People call these numbers binomial coefficients, since you can also get them like this:

$(x + y)^5 = x^5 + 5 x^4 y + 10 x^3 y^2 + 10 x^2 y^3 + 5 x y^4 + y^5$

We get the 10 in $10 x^3 y^2$ here because there are 10 ways to take 5 things and choose 3 to call x’s and 2 to call y’s. In general we have

$\displaystyle{ (x + y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k} }$

where the binomial coefficient $\binom{n}{k}$ is the kth number on the nth row of Pascal’s triangle. Here count both rows and the numbers in a row starting from zero.

Since we can permute n things in

$n! = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot n$

ways, there are

$\displaystyle{ \frac{n!}{k! (n-k)!} }$

ways to take n things and choose k of them to be x’s and (n-k) of them to be y’s. You see, permuting the x’s or the y’s doesn’t change our choice, so we have to divide by $k!$ and $(n-k)!.$

So, the kth number in the nth row of Pascal’s triangle is:

$\displaystyle{\binom{n}{k} = \frac{n!}{k! (n-k)!} }$

All this will be painfully familiar to many of you. But I want everyone to have an fair chance at understanding the next section, where we’ll see something nice about Pascal’s triangle and the number

$e \approx 2.718281828459045...$

The hidden e in Pascal’s triangle

In 2012, a guy named Harlan Brothers found the number e hiding in Pascal’s triangle… in a very simple way!

If we add up all the numbers in the nth row of Pascal’s triangle we get $2^n$ . But what if we take the product of all these numbers? Let’s call it $t_n.$ Then here’s what Brothers discovered:

$\displaystyle{ \lim_{n \to \infty} \frac{t_n t_{n+2}}{t^2_{n+1}} = e }$

This may seem mysterious, but in fact it’s rather simple once you see the trick. I’ll use a nice argument given by Greg Egan.

We’ve said $t_n$ is the product of all numbers in the nth row of Pascal’s triangle. Just for fun, let’s divide this by the product of all numbers in the next row:

$\displaystyle{ u_n = \frac{t_n}{t_{n+1}} }$

And since this is so much fun, let’s do it again! Divide this quantity by its next value:

$\displaystyle{ v_n = \frac{u_n}{u_{n+1}} }$

Now look:

$\displaystyle{v_n = \frac{t_n/t_{n+1}}{t_{n+1}/t_{n+2}} = \frac{t_n t_{n+2}}{t_{n+1}^2} }$

So, this is the thing that should approach e.

But why does it approach e? To see this, first take Pascal’s triangle and divide each number by the number to its lower left. We get a second triangle of numbers. Then take each number in this second triangle and divide it by the number to its lower right! We get a third triangle, like this:

If you think a bit, you’ll see:

• In the first triangle, the product of all numbers in the nth row is $t_n.$

• In the second, the product of all numbers in the nth row is $u_n.$

• In the third, the product of all numbers in the nth row is $v_n.$

And look—there’s a cool pattern! In the third triangle, all the numbers in any given row are equal. In the row with n numbers, all those numbers equal

$\displaystyle{ (n+1)/n = 1 + \frac{1}{n} }$

So, the product of all these numbers is

$\displaystyle{ \left(1 + \frac{1}{n}\right)^n }$

But it’s a famous fact that

$\displaystyle{ \lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n = e}$

Some people even use this as a definition of e. So,

$\displaystyle{ \lim_{n \to \infty} v_n = e}$

which is just what we wanted!

Puzzle 1. Use the formula I mentioned:

$\displaystyle{\binom{n}{k} = \frac{n!}{k! (n-k)!} }$

to show all the numbers in the same row of the third triangle are equal.

Triangular numbers

The number of balls in a triangular stack with n balls at the bottom is called the nth triangular number,

$T_n = 1 + 2 + \cdots + n$

If you chop a square of balls in half along a diagonal you get a triangle, so $T_n$ is approximately half the nth square number:

$\displaystyle{ T_n \approx \frac{n^2}{2} }$

But if you chop the square in half this way, the balls on the diagonal get cut in half, so to get the nth triangle number we need to include their other halves:

$T_n = \displaystyle{ \frac{n^2}{2} + \frac{n}{2} = \frac{n(n+1)}{2} }$

These numbers go like

$1, 3, 6, 10, \dots$

and they are one of the simple pleasures of life, like sunshine and good bread. Spotting them in a knight-move zigzag pattern in the multiplication table was one of my first truly mathematical experiences. You can also see them in Pascal’s triangle:

because

$T_n = \displaystyle{ \binom{n+1}{2} }$

But today it’s time to see how $T_n$ is related to $t_n$ , the product of all the numbers in the nth row of Pascal’s triangle!

If we subtract each triangular number from the the one before it we get the numbers $-n$ , and if we subtract each of these numbers from the one before it we get the number 1. This should remind you of something we’ve seen:

$\displaystyle{ u_n = \frac{t_n}{t_{n+1}} }$

$\displaystyle{ v_n = \frac{u_n}{u_{n+1}} }$

$\displaystyle{ \lim_{n \to \infty} v_n = e }$

Here we’re dividing instead of subtracting. But if take logarithms, we’ll be subtracting, and we get

$\ln(u_n) = \ln(t_n) - \ln(t_{n+1})$

$\ln(v_n) = \ln(u_n) - \ln(u_{n+1})$

$\displaystyle{ \lim_{n \to \infty} \ln(v_n) = 1 }$

What can we do with this? Well, suppose $\ln(v_n)$ were equal to 1, instead of approaching it. Then $\ln(t_n)$ could be the nth triangular number… and we’d get a cool formula for the product of all numbers in the nth row of Pascal’s triangle!

But since $\ln(v_n)$ is just approximately equal to 1, we should only expect an approximate formula for the product of all numbers in the nth row of Pascal’s triangle:

$\ln(t_n) \approx T_n$

$\displaystyle{ t_n \approx e^{T_n} = e^{n(n+1)/2} }$

This was my hope. But how good are these approximations? I left this as a puzzle on Google+, and then Greg Egan stepped in and solved it.

For starters, he graphed the ratio $\ln(t_n)/T_n,$ and got this:

That looks pretty good: it looks like it’s approaching 1. But he also graphed the ratio $t_n/e^{T_n},$ and got this:

Not so good. Taking exponentials amplifies the errors. If we want a good asymptotic formula $t_n,$ we have to work harder. And this is what Egan did.

Digging deeper

So far we’ve talked a lot about $t_n,$ the product of all numbers in the nth row in Pascal’s triangle… but we haven’t actually computed it. Let’s try:

$\begin{array}{ccl} t_n &=& \displaystyle{ \binom{n}{0} \cdot \binom{n}{1} \cdot \cdots \cdot \binom{n}{n} } \\ \\ &=& \displaystyle{ \frac{n!}{0! \cdot n!} \cdot \frac{n!}{1! \cdot (n-1)!} \cdot \cdots \cdot \frac{n!}{n! \cdot 0!} } \\ \\ &=& \displaystyle{ \frac{(n!)^{n+1}}{\left(0! \cdot 1! \cdot \cdots \cdot n!\right)^2} } \end{array}$

So, we’re seeing the superfactorial

$\displaystyle{ 0! \cdot 1! \cdot \cdots \cdot n! }$

raise its pretty head. This is also called the Barnes G-function, presumably by people who want to make it sound more boring.

Actually that’s not fair: the Barnes G-function generalizes superfactorials to complex numbers, just as Euler’s gamma function generalizes factorials. Unfortunately, Euler made the mistake of defining his gamma function so that

$\Gamma(n) = (n-1)!$

when $n = 1, 2, 3, \cdots.$ Everyone I trust assures me this was a bad idea, not some deep insight… but Barnes doubled down on Euler’s mistake and defined his G-function so that

$G(n) = 0! \cdot 1! \cdot \cdots \cdot (n-2)!$

So, we’ll have to be careful when looking up formulas on Wikipedia: the superfactorial of n is $G(n+2).$ Thus, we have

$\displaystyle{ t_n = \frac{(n!)^{n+1}}{G(n+2)^2} }$

$\displaystyle{ \ln(t_n) = (n+1) \ln (n!) - 2 \ln G(n+2) }$

Now, there’s a great approximate formula for the logarithm of a factorial. It’s worth its weight in gold… or at least silver, so it’s called Stirling’s formula:

$\displaystyle{ \ln(n!) = n \ln (n) \; - \; n \; + \;\tfrac{1}{2} \ln(2 \pi n) \; + \; \frac{1}{12n} \cdots }$

where the dots mean stuff that goes to zero when divided by the last term, in the limit $n \to \infty.$

There’s also an approximate formula for the logarithm of the superfactorial! It’s a bit scary:

$\begin{array}{ccl} \ln G(n+2) &=& \displaystyle{ \left(\tfrac{1}{2} \ln(n+1) - \tfrac{3}{4}\right) (n+1)^2 \; + } \\ \\ && \tfrac{\ln(2\pi)}{2} \, (n+1) \; - \\ \\ && \tfrac{1}{12} \ln(n+1) \; + \\ \\ && \tfrac{1}{12} - \ln A \; + \cdots \end{array}$

where the dots mean stuff that actually goes to zero as $n \to \infty.$

What’s A? It’s the Glaisher–Kinkelin constant! If you’re tired of memorizing digits of pi and need a change of pace, you can look up the first 20,000 digits of the Glaisher–Kinkelin constant here, but roughly we have

$A \approx 1.282427129100622636875342...$

Of course most mathematicians don’t care much about the digits; what we really want to know is what this constant means!

Euler, who did some wacky nonrigorous calculations, once argued that

$\displaystyle{ 1 + 2 + 3 + \cdots = -\tfrac{1}{12} }$

Riemann made this rigorous by defining

$\displaystyle{ \zeta(s) = 1^{-s} + 2^{-s} + 3^{-s} + \cdots }$

which converges when $\mathrm{Re}(s) > 1,$ and then analytically continuing this to other values of $s.$ He found that indeed

$\displaystyle{ \zeta(-1) = -\tfrac{1}{12} }$

This fact has many marvelous ramifications: for example, it’s why bosonic string theory works best in 24 dimensions! It’s also connected to the $\tfrac{1}{12n}$ term in Stirling’s formula.

But anyway, we might wonder what happens if we compute $\zeta(s)$ for $s$ near -1. This is where the Glaisher–Kinkelin constant shows up, because if we try a Taylor series we get

$\displaystyle{ \zeta'(-1) = \tfrac{1}{12} - \ln A }$

To me, this means that $\tfrac{1}{12} - \ln A$ is more fundamental than A itself, and indeed you’ll see it’s this combination that shows up in the approximate formula for superfactorials. So, we can simplify that formula a bit:

Now, let’s use this together with Stirling’s formula to estimate the logarithm of the product of all numbers in the nth row of Pascal’s triangle. Remember, that’s

$\displaystyle{ \ln(t_n) = (n+1) \ln (n!) - 2 \ln G(n+2) }$

So, we get

$\begin{array}{ccl} \ln(t_n) &\approx& \displaystyle{(n+1)\Big[ n \ln(n) - n + \tfrac{1}{2} \ln(2 \pi n) + \frac{1}{12n} \Big] } \\ \\ && - \displaystyle{ \Big[ \left( \ln(n+1) - \tfrac{3}{2}\right) (n+1)^2 + \ln(2\pi) \cdot (n+1) -} \\ \\ && \quad \displaystyle{ \tfrac{1}{6} \ln(n+1) + 2\zeta'(-1) \Big] } \end{array}$

and exponentiating this gives a good approximation to $t_n.$

Here is a graph of $t_n$ divided by this approximation, created by Egan:

As you can see, the ratio goes to 1 quite nicely!

So, we’ve seem some nice relationships between these things:

$1 + 2 + \cdots + n = T_n$

$1 \cdot 2 \cdot \cdots \cdot n = n!$

$\binom{n}{1} \cdot \binom{n}{2} \cdot \cdots \cdot \binom{n}{n} = t_n$

$1! \cdot 2! \cdot \cdots \cdot n! = G(n+2)$

$\frac{1}{0!} +\frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots = e$

and Euler’s wacky formula

$\displaystyle{ 1 + 2 + 3 + \cdots = -\tfrac{1}{12} }$

Puzzle 2. Can you take the formula

and massage it until it looks like $n(n+1)/2$ plus ‘correction terms’? How big are these correction terms?

References

Any errors in the formulas above are my fault. Here are the papers that first squeezed e out of Pascal’s triangle:

• Harlan J. Brothers, Pascal’s triangle: The hidden stor-e, The Mathematical Gazette, March 2012, 145.

• Harlan J. Brothers, Finding e in Pascal’s triangle, Mathematics Magazine 85 (2012), 51.

I learned the idea from here, thanks to Richard Elwes:

• Alexander Bogomolny, e in the Pascal Triangle, Interactive Mathematics Miscellany and Puzzles.

For how Euler derived his crazy identity

$\displaystyle{ 1 + 2 + 3 + \cdots = -\tfrac{1}{12} }$

and how it’s relevant to string theory, try:

• John Baez, My favorite numbers: 24.

]]>