A programmer’s proof of the triangular numbers

A programmer’s proof of the triangular numbers – Andy G's BlogSkip to content Skip to menu

The triangular numbers are an interesting mathematical phenomenon that appears constantly in computer science. When you, the programmer, talk about the Big-Oh complexity of a nested for loop that gets executed $1 + 2 + \ldots + n$ times, you might just slap $O(n^2)$ on it and call it a day.

But do you ever think about what that summation actually is? In this article I’ll present an alternative formulation of the series that I think is satisfying from a programmer’s point of view, and also present some interesting results from looking at the series in different ways.

(Note: this article was originally written in $\LaTeX$ and transcribed to WordPress. Get it as a .pdf here)

What are the triangular numbers?

Consider the following algorithm:

How many times does Foo() execute? Let’s just walk through the case where $n = 2$ .

$i = 0$ , $j = 0$ Foo();
$i = 1$ , $j = 0$ Foo();
$i = 1$ , $j = 1$ Foo();
$i = 2$ , stop

So, when $n = 2$ , Foo() will be executed 3 times. What sort of pattern did it follow, though? Let’s break it down:

first iteration: 1 time ( $i=0$ case)
second iteration: 2 times ( $i=1$ case)

It would be reasonable to assume that this pattern continues. That is, for $n$ iterations we will see the following pattern:

iteration 1: 1 time
iteration 2: 2 times
iteration 3: 3 times
$\ldots$
iteration $n-1$ : $n-1$ times
iteration $n$ : $n$ times

So the total number of times Foo() gets called is

$1 + 2 + \ldots + n$

Which we’ll wrap up nicely as the following summation:

$\sum\limits_{i=1}^n i$

A visualization

At this point you may be saying “Yes, I understand what the summation looks like, but what does it sum up to!?”, and I’m getting to that. If you will, though, please allow me one more aside. Let’s look at a visualization of this series.

Triangular numbers for n=5

Now you see why they’re called the triangular numbers. Most visualizations will show you them in this format.

The geometric proof

Perhaps the most common visual approach to computing triangular numbers is with some geometric help. You see, the triangular numbers, being a Figurate Number (sometimes called a Polygonal Number), are easy to visualize. To compute the triangular numbers using some geometric help, let us first recognize that a (right) triangle is half of a square.

A 5×5 square of dots

A 5x5 square of dots, with our triangle highlighted in red (as a right triangle)

A 5×5 square of dots, with our triangle highlighted in red (as a right triangle)

Next, we recognize that the number of dots in the square is equal to its area, or simply the number of dots along one side multiplied by itself. More formally, the area of an $n$ by $n$ square is $n \times n = n^2$ . For our 5×5 square, this gives 25 dots.

$n^2$ gives us the area of a square, and $\frac{n^2}{2}$ gives us half of it. But check out the figure below! Taking just half of the area only gives us half of the dots along the diagonal of the square! We want all of the dots along the diagonal of the square.

Taking half the square doesn’t quite give us all the dots in our triangle

How many dots are in the diagonal of a square? Well, there’s one dot for each row in the triangle, therefore there are $n$ dots, and we only captured half of their areas when we got $\frac{n^2}{2}$ so we need to add in that other $\frac{n}{2}$ giving us a final computed number of dots as $\frac{n^2 + n}{2}$ , or simplified as $\frac{n \times (n+1)}{2}$ , which is the commonly used formula for computing triangular numbers, and is the exact summation we will get in the next section when approaching the summation from another angle.

Pretty awesome, right?

In this section we’ll actually derive the result of the summation in a novel way. A way that might appeal to a programmer who has to constantly look at loops all day.

I’ll pose a question to you:

“How many times can you make $n$ from the series?”

For the purpose of our “programmer’s proof”, let’s consider a slightly different visualization of the series than we saw in the previous section First, we’ll make our equilateral triangle a right triangle

Visualization of triangular numbers as a right triangle

Next, we’ll take the top of the triangle and align it to the gaps below

Alternative representation of triangular numbers of n=5

A little weird, huh? However, I think it helps us to answer our question. (We’ll play Tetris with it in the next subsection!) Let’s answer the question of “How many times can we get $n$ dots from our triangle?” Trivially, we can do it at least once, because the very last row has $n$ dots in it. The second last row has $n - 1$ , and conveniently we can see that the first row only has $1$ , so we can combine them to obtain $n$ for a second time.

Finally, we notice that the second and third rows added together also equal $n$ . So we’ve made $n$ three times for $n = 5$ . The implication is that the triangular number summation for $n=5$ is $3n = 3 * 5 = 15$ . Nice. Let’s try to derive a formula.

For $n$ elements, how many times can we make $n$ ? Start pulling terms simultaneously off the left and right ends of

$0 + 1 + 2 + 3 + \ldots + (n-3) + (n-2) + (n-1) + n$

Notice I made a bit of a modification to the series by adding $0$ to it. Now we have $n+1$ terms in our series instead of $n$ . Adding the $0$ term does not change the value of the summation; all we’re saying is that the triangular numbers for $n$ will result in a series containing $n+1$ terms.

Pulling from both sides at once, we get the following summations:

$n + 0$
$(n-1) + 1$
$(n-2) + 2$
$(n-3) + 3$
$\ldots$
$(n - \lfloor\frac{n}{2}\rfloor + \lceil\frac{n}{2}\rceil$

So, for a sequence of n items, we can make a sum of $n$ exactly $\frac{n+1}{2}$ times, leading to the solution of

$\frac{n \times (n+1)}{2}$

As a programmer, I find this a very satisfying approach. It feels like we’re writing a method to perform the computation in $O(\frac{n}{2})$ time instead of $O(n)$ time.

Tetris!

Let’s visualize what we just did by playing Tetris.

Take our alternative figure of a triangle from above and horizontally flip the portion we set aside

After flipping the top portion horizontally
Then we’ll flip it vertically. Now we can see that it will fit very nicely in the gaps with the rest of the dots.

After flipping the top portion vertically
Translate the portion down, giving us a nice rectangle that is $n$ long by $\frac{n+1}{2}$ tall, whose area is $\frac{n \times (n+1)}{2}$ (look familiar!?!?).

After translating the top portion vertically to fit the rest of the triangle, we have a convenient rectangle from which we can easily compute the number of dots contained within

An observation

(Author’s note: Feel free to skip this section, it gets a little mathy)

Approaching the summation from the other side:

$n + (n-1) + (n-2) + \ldots (n-(n-1))$

is a little more challenging, but it yields an interesting series that is equivalent to our derived $\frac{n\times(n+1)}{2}$ from previous sections.

Let’s first try to factor out $n$ :

$n(1 + \frac{n-1}{n} + \frac{n-2}{n} + \ldots + \frac{n-(n-1)}{n})$

And the last term evaluates to $\frac{1}{n}$ , so we have:

$n(1 + \frac{n-1}{n} + \frac{n-2}{n} + \ldots + \frac{1}{n})$

Which may not appear very interesting at first. Let’s begin combining terms in the interior and see what we can come up
with:

$n(\frac{n}{n} + \frac{n-1}{n} + \ldots + \frac{1}{n}) = n(\frac{n+(n-1)}{n} + \ldots + \frac{1}{n})$

Aha! Now we’re getting somewhere. Let’s simplify the first term in the parenthesis:

$n(\frac{2n - 1}{n} + \frac{n-2}{n} + \ldots + \frac{1}{n})$

And add the next term into the first term (we’re starting to see a pattern emerging)

$n(\frac{3n - 3}{n} + \frac{n-3}{n} + \ldots + \frac{1}{n})$

As we combine our terms, the coefficient on $n$ within the parentheses grows by $1$ for each new term, and given that there are $n$ terms in parentheses (we factored out $n$ , we didn’t remove it altogether), we can deduce that the final coefficient will be $n$ .

As for the right hand side of the difference, it appears to be growing as $1 + 2 + 3 + \ldots + n-1$ , which is again our triangular numbers, just up to $n-1$ ! The formula begins to look like this:

$n(\frac{n^2 - (\sum_{i=1}^{n-1} i}{n}))$

Which we can simplify by distributing the $n$ term through the parenthesis, giving a new solution of

$n^2 - (\sum_{i=1}^{n-1} i)$

Which ostensibly will cause a repetition of what we just did, giving:

$n^2 - ((n-1)^2 - (\sum_{i=1}^{n-2} i))$

And so on. Eventually we stop at the last term, which is $1$ , so, for $n=5$ our series looks like this:

$n^2 - ((n-1)^2 - ((n-2)^2 - ((n-3)^2 - (1))))$

And when we distribute the subtraction, we get an interesting alternating series that looks like this:

$n^2 - (n-1)^2 + (n-2)^2 - (n-3)^2 + 1$

Just as a sanity check, we can fill in the actual values:

$25 - 16 + 9 - 4 + 1$

Which clearly sums to $15$ , the same as if we applied our magic $\frac{n\times(n+1)}{2}$ formula.

Let’s formalize our alternating series as

$\sum_{i=0}^{n} (-1^{i})\times (n-i)^2$

And now formally state the equivalence between our two series:
(Proof by the commutative property of addition)

$\sum\limits_{i=1}^n i \equiv \sum_{i=0}^{n} (-1^{i})\times (n-i)^2$

Which is really a fancy way of saying

$1 + 2 + \ldots + n = n + (n-1) + \ldots + 1$

I think this revelation is the most interesting part of the entire article! (Okay, playing Tetris to prove the summation of the triangular numbers was also pretty awesome.)

Closing thoughts

The triangular numbers are a series that appears all the time in your average programmer’s life, without them really realizing it. It’s easy to write off the summation’s value as “some value less-than-or-equal-to $n^2$ “, but understanding the summation a little more deeply can also bear fruit, like the solution to a common interviewing problem.

Thank you for reading and sharing a love of all things technical.

A programmer’s proof of the triangular numbers

What are the triangular numbers?

A visualization

The geometric proof