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 times, you might just slap 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 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 .

- , Foo();
- , Foo();
- , Foo();
- , stop

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

- first iteration: 1 time ( case)
- second iteration: 2 times ( case)

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

- iteration 1: 1 time
- iteration 2: 2 times
- iteration 3: 3 times
- iteration : times
- iteration : times

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

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

**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.

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.

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 by square is . For our 5×5 square, this gives 25 dots.

gives us the area of a square, and 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.

How many dots are in the diagonal of a square? Well, there’s one dot for each row in the triangle, therefore there are dots, and we only captured half of their areas when we got so we need to add in that other giving us a final computed number of dots as , or simplified as , 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?

**A programmer’s proof of the triangular numbers**

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 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

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

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 dots from our triangle?” Trivially, we can do it at least once, because the very last row has dots in it. The second last row has , and conveniently we can see that the first row only has , so we can combine them to obtain for a second time.

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

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

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

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

So, for a sequence of n items, we can make a sum of exactly times, leading to the solution of

As a programmer, I find this a very satisfying approach. It feels like we’re writing a method to perform the computation in time instead of 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
- 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.
- Translate the portion down, giving us a nice rectangle that is long by tall, whose area is (look familiar!?!?).

**An observation**

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

Approaching the summation from the other side:

is a little more challenging, but it yields an interesting series that is equivalent to our derived from previous sections.

Let’s first try to factor out :

And the last term evaluates to , so we have:

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

with:

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

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

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

As for the right hand side of the difference, it appears to be growing as , which is again our triangular numbers, just up to ! The formula begins to look like this:

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

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

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

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

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

Which clearly sums to , the same as if we applied our magic formula.

Let’s formalize our alternating series as

And now formally state the equivalence between our two series:

*(Proof by the commutative property of addition)*

Which is really a fancy way of saying

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 “, 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.

Tags: Big-O Notation, figurate number, Polygonal number, Power series, proof, Triangular numbers

## Leave a Reply