Skip to main content

The hollow triangular numbers are divisible by three

You might be familiar with the triangular numbers: the number of objects that form equilateral triangles like this:

The sequence is 3, 6, 10, 15, 21, ... The first one, 3, is 1 + 2, the second one, 6, is 1 + 2 + 3, the third one, 10, is 1 + 2 + 3 + 4 and so on. For a triangle with a base of \(n\) blobs the number of blobs in the triangle is \(n * (n + 1) / 2\) (which can be proved by various means and was famously figured out by the mathematician Gauss while a school boy).

But what about the hollow triangular numbers? The ones where you take the middle blobs out of the triangles and just leave the border. Like this:
The pattern there is very simple. They are all multiples of three. And the formula would be that the hollow triangle with a base of size \(n\) has \(3 * (n-1)\) blobs in it (and since that's a multiple of three so is the number of blobs in a hollow triangle).

Here are three ways to prove that that formula is correct.

Subtracting the middle

Because we already have a formula for the filled in triangle (see above) we can use it to figure out the formula for the hollow triangle. Look at the triangle with a base of 6 blobs.

You can see that the number of blobs in the hollow triangle with a base of six is the number of blobs in the filled in triangle of base six minus the number of blobs in the filled in triangle of base three. Or, more, generally the number of blobs in a hollow triangle of base \(n\) is

\[\begin{aligned}
&n * (n+1) / 2 - (n-3) * (n-3 + 1) / 2 \\
&= 1/2 * (n^2 + n - n^2 + 5n - 6) \\
&= (6n - 6)/2 \\
&= 3 * (n - 1) \\
\end{aligned}\]
Which is the formula above.

Counting around the outside

Another way is to follow around the edge of a triangle and observe that, for example, for the hollow triangle with a base of six the total number of blobs is \(6 + 5 + 4\) (the blue blobs, plus the red blobs, plus the yellow blobs).

And the more general formula would be that for a hollow triangle of base \(n\) the total number of blobs is \(n + (n-1) + (n - 2)\) which simplifies to \(3 * (n - 1)\).

Mathematical induction

But a real mathematician is likely to prove this in a different way using mathematical induction. That works by beginning with some starting case that can be seen to meet the required statement and a way of going from one case to another.

For example, it's pretty clear that the hollow triangle with four blobs in its base (see above) has nine blobs in total and since nine is divisible by three the statement we are trying to prove 'all hollow triangular numbers are divisible by three' is at least true for it.

Then you just need a way of working up from there. For example, if there was a way to prove that the next hollow triangular number is divisible by three if we know that the previous one was, it would be possible to know that they all were. That's because you'd start with the hollow triangle with four blobs in the base and know that the one with five blobs was divisible by three and then you'd know that the one with six blobs was divisible by three and so on... forever.

So, all you need is to examine one step in this infinite chain of reasoning.

First let's say that \(hollow_n\) is the number of blobs in the hollow triangle with a base containing \(n\) blobs. And let's assume that it is divisible by three. For mathematical induction to be applicable we just need to show that \(hollow_{n+1}\) (the next hollow triangular number) is divisible by three. So, we just need to know how to go from \(hollow_n\) to \(hollow_{n+1}\).

Take a look at the following diagram showing the hollow triangular number with base six (on the left).

You can think of going from \(hollow_6\) to \(hollow_7\) as the same adding a row of seven blobs (on the right) and removing the inside of the old bottom row (coloured in red). So, \(hollow_7 = hollow_6 + 7 - 4\) which simplifies to \(hollow_7 = hollow_6 + 3\). Since we've added three and know that \(hollow_6\) is divisible by three we know that \(hollow_7\) is also.

That can easily be generalized \(hollow_{n+1} = hollow_n + (n+1) - (n-2)\) (added on a row of \(n+1\) at the bottom and removed the interior \(n-2\) blobs leaving just the two blobs on the outside). That simplifies to \(hollow_{n+1} = hollow_n + 3\). And so if we know that \(hollow_n\) is divisible by three then so is \(hollow_{n+1}\) and thus by mathematical induction we know that all hollow triangular numbers are divisible by three.

Back to the triangular numbers

Now that we've got the idea of mathematical induction it's possible to return to a claim a made at the start: for the filled in triangles the number of blobs is \(n * (n + 1) / 2\) when the base has \(n\) blobs. That too can be proved by induction.

The starting case is a base of two blobs. Just by looking at it we can see that it has three blobs in the triangle and \(2 * (2 + 1) / 2 = 3\). So the formula works for that case.

Then consider going from a triangle with a base of \(n\) blobs to one with \(n+1\). All that happens there is that \(n+1\) blobs get added (the new bottom row). So, if the triangle with a base of \(n\) blobs has \(n * (n + 1) / 2\) in total, the triangle with base \(n +1\) has \(n * (n + 1) / 2 + (n + 1)\) which can be simplified as follows:

\[\begin{aligned}
&n * (n + 1) / 2 + n + 1 \\
&= 1/2(n * (n +1) + 2(n+1)) \\
&= 1/2(n^2 + n + 2n + 2) \\
&= 1/2(n^2 + 3n + 2) \\
&= 1/2(n+1)(n+2) \\
&= (n+1) * ((n+1)+1)/2
\end{aligned}\]
Which is just what was expected.

PS I spotted all this staring at the duvet cover the other night. But then again there was that flight I took back in 2008.

PPS In the comments reader tz points out another way to see that the number of blobs in a hollow triangle is a multiple of three. There are three corners and three equal length sides (when ignoring the corners).


Comments

tz said…
Also in each case, the length of each side is equal, but the corners are shared, so the number will be the length of one side minus one, multiplied by three. Or since the lengths are identical, the non-corners will be 3N, and 3 corners, which would also be a multiple o 3.
Brian Oxley said…
This comment has been removed by the author.
Brian Oxley said…
(Reposted to fix thinko.)

@tz I would describe it as each larger triange adds another ball to each corner. Three corners is three balls. The starting case is the "null triangle" consisting of no balls.

This generalizes to any hollow regular polygon. Balls increase as multiples of the number of sides.
Wolfkeeper said…
This is highly related to the method of differences:

http://en.wikipedia.org/wiki/Difference_engine#Method_of_differences

That's how Babbage was going to tabulate polynomials.

IRC the difference between (X+1)^n and X^n is O(X^n-1) so you can calculate successive polynomials in O(n) time using simple adding and multiplying by (often small) constants n times.
CandorZ said…
Nice Article...
As descriptive as any one can want it!
Andywal said…
It would have been nice if you had gone just one step further to prove how many blobs make up a pyramid of base(n) blobs.
@Andywal: sounds like a good 'exercise for the reader'
Xapp said…
@tz This is the first solution I came up with too. Algebraically:
3 * (n - 2) + 3 = x

And after some manipulation:
(n - 2) + 1 = x/3
n - 2 = x/3 - 1
n = x/3 + 1
n - 1 = x/3
3 (n - 1) = x

Fun stuff.

=D
Dan Sutton said…
Ummm... the proof that they're multiples of three is obvious: to make the next bigger triangle, you add one dot to each side, thus three dots - it's impossible to make one that isn't a multiple of three!
Dan Sutton said…
In other words, the total number of dots = 3 x (1 vertex + 1 side). This is the same as saying 3n = a multiple of 3. I don't think you really require a proof for that... and it works for any n-sided polygon, if you think about it.

Popular posts from this blog

Your last name contains invalid characters

My last name is "Graham-Cumming". But here's a typical form response when I enter it:


Does the web site have any idea how rude it is to claim that my last name contains invalid characters? Clearly not. What they actually meant is: our web site will not accept that hyphen in your last name. But do they say that? No, of course not. They decide to shove in my face the claim that there's something wrong with my name.

There's nothing wrong with my name, just as there's nothing wrong with someone whose first name is Jean-Marie, or someone whose last name is O'Reilly.

What is wrong is that way this is being handled. If the system can't cope with non-letters and spaces it needs to say that. How about the following error message:

Our system is unable to process last names that contain non-letters, please replace them with spaces.

Don't blame me for having a last name that your system doesn't like, whose fault is that? Saying "Your last name …

All the symmetrical watch faces (and code to generate them)

If you ever look at pictures of clocks and watches in advertising they are set to roughly 10:10 which is meant to be the most attractive (smiling!) position for the hands. They are actually set to 10:09.14 if the hands are truly symmetrical. CC BY 2.0image by Shinji
I wanted to know what all the possible symmetrical watch faces are and so I wrote some code using Processing. Here's the output (there's one watch face missing, 00:00 or 12:00, because it's very boring):



The key to writing this is to figure out the relationship between the hour and minute hands when the watch face is symmetrical. In an hour the minute hand moves through 360° and the hour hand moves through 30° (12 hours are shown on the watch face and 360/12 = 30).
The core loop inside the program is this:   for (int h = 0; h <= 12; h++) {
    float m = (360-30*float(h))*2/13;
    int s = round(60*(m-floor(m)));
    int col = h%6;
    int row = floor(h/6);
    draw_clock((r+f)*(2*col+1), (r+f)*(row*2+1), r, h, floor(m…

The Elevator Button Problem

User interface design is hard. It's hard because people perceive apparently simple things very differently. For example, take a look at this interface to an elevator:


From flickr

Now imagine the following situation. You are on the third floor of this building and you wish to go to the tenth. The elevator is on the fifth floor and there's an indicator that tells you where it is. Which button do you press?

Most people probably say: "press up" since they want to go up. Not long ago I watched someone do the opposite and questioned them about their behavior. They said: "well the elevator is on the fifth floor and I am on the third, so I want it to come down to me".

Much can be learnt about the design of user interfaces by considering this, apparently, simple interface. If you think about the elevator button problem you'll find that something so simple has hidden depths. How do people learn about elevator calling? What's the right amount of informati…