Of course, it wouldn’t hurt to get something on this blog.  I’m thinking about it.  Just busy.

1. I write a list of numbers on a grid (e.g. the numbers 1 to 105 on a 7-by 15 grid)
2. They circle “2″ with a color, then mark out all of the even numbers with that color.
3. The circle “3″ with a different color, and mark out every third number with the new color.
4. Continue like this for 5, 7, 11, etc.  Always circle the next number that hasn’t been colored with a new color.

As you do this, you will find interesting patterns that speed up the coloring and teach you a bit about numbers.  It is interesting to try grids with different widths and find new patterns too.

Eventually I got tired of writing these grids out by hand, so I wrote a little web page to do it for me.  It colors the grid too — try it!

This opens the door to a little bit more fun. Remember that

So we know

Let’s arrange the terms on top of each other, like this

Now if we group the terms that are on top of each other, we se we can write

OR

And we see that the n-th square number is just the sum of the first n odd numbers!

Now in pictures

There are other ways to see this. This set of figures shows how we can build larger squares by adding borders to smaller squares:

Building squares by adding odd numbers

When we add the border to an n-by-n square to make a (n+1)-by-(n+1) square, we need to add n squares to one side, n squares to the top, and then we need to add one square to the top corner to complete it.  Altogether, we add 2n + 1 squares.  2n + 1 is just the (n+1)th odd number. 

If we start from 0, then add 1, then add 3, then add 5, and so on — adding the n-th odd number at the n-th step — we’ll find that after n steps the sum is just .  Or

Just like we saw before.

The ‘picture part’ of this argument is really just a special case of Proposition II.4 in Euclid’s Elements:

 If a straight line is cut at random, then the square on the whole equals the sum of the squares on the segments plus twice the rectangle contained by the segments.

(follow the link for the proof, discussion, and an interactive diagram.)  In fact, Euclid’s Book II is full of this sort of Geometric Algebra – identities that are easy to write down formally once you know Algebra, but turn out to have straightforward interpretations in Geometry.

An easier way

After all of that work, I do want to make sure you know how easy it is to do this with Algebra:

So the n-th square number is just the (n-1)-th square number plus the n-th odd number.  Unlike the geometric result, this works seamlessly for negative numbers, complex numbers, or for elements of any other field.  Maybe that’s why we hear more about Algebraic Geometry than Geometric Algebra.

That’s not the whole story

The pictures and formulas I’ve put together in this post were meant to be convincing, but they are explanations, not proofs.  This is largely because I am using figurate numbers to teach elementary aged kids about Arithmetic, Geometry, and surprising connections between them. But if you really want to be sure about things, you need to know that there is a little problem I’ve been sweeping under the rug.

We want to prove that the n-th square number is the sum of the first n odd numbers.  All we have proven is that , then I wave my hands and say that “we start from zero and keep adding odd numbers, and we’ll just move from one odd number to the next”. 

We come across this situation all of the time in Mathematics: we have a process, we understand what it does in one step, and we want to make a statement about what it does after an arbitrary number of steps.  To do this, we need to use mathematical induction.  It may sound a bit intimidating at first, but it is really just a way to formalize the common-sense-hand-waving I’ve been doing (and to make sure our common sense doesn’t get us into trouble). 

I’ll defer discussing induction for a while.  It is worth a few posts on its own, and we’ll find that there are good reasons to be a little skeptical of our common sense.

We all know that we can split a square into two equal triangles by drawing a line down the diagonal:

Breaking a square into two triangles

When we try this for the “blocky” triangles we used to build our triangle numbers, it doesn’t quite work.  Have a look at what happens for the “4-triangle”:

A rectangle from two equal triangles

We get a 4-by-5 rectangle rather than a square. If you play around with it a little bit, you should be able to convince yourself that whenever we put two equal triangles together, we’ll get a rectangle.  Two “3-triangles” form a 3-by-4 rectangle, two “2-triangles” form a 2-by 3 rectangle, and two “1-triangles” form a 1-by-2 rectangle.  Similarly, two “50-triangles” will form a 50-by-51 rectangle, and two “100-triangles” will form a 100-by-101 rectangle.

An aside: notation and definitions

Notice that I’ve introduced a little bit of vocabulary here.  I need a way to talk about these different shapes, so I called them “n-triangles” where n is any positive whole number.  I haven’t defined this formally, so I’m relying on intuition here and that is not a best practice!  I’m going to need another bit of notation before carrying on.

Definition: The n-th triangle number is the sum of the first n positive whole numbers, and it will be written .

This is just restating what we already know, and adding some new notation — we can now just write for the n-th triangle number.  So and so on.

Back to the shapes

With this new notation in hand, we can start writing down some interesting Math.  We observed that we can put together two n-triangles to make an n-by-(n+1) rectangle.  This just means

Or

How about that?  So we could take and see that

Or we could take and see that

So .  Wow, that was easy.  Now what is ?

Building Squares

You might have noticed when we put two equal triangles together to build a rectangle, we could have built a perfect square if we had just used a smaller triangle.  Here are the first few examples:

Squares from triangles

So we have a new formula:

We could have come up with this using a bit of algebra too:

Here we used the fact that .  Think about it for a bit if you don’t see why.

Turning it into an Arithmetic drill

Sometimes I like to incorporate little identities like the ones we’re playing with here into my kids Arithmetic practice.  Here is an example of a problem set I gave them before I introduced the idea of “triangle numbers”:

The problems on the left side are just asking you compute , the problems on the left side ask you to compute . We know that these are equal.

My boys worked through this, noticed the patterns and realized that there must be something deeper going on behind the scenes. After they finished the exercise, I started drawing pictures for them — almost exactly like the ones I produced above — and they lit up right away when they understood the real story the arithmetic was trying to tell.

I like it when I can create a little tension, and make them really want to answer a question before presenting the meat of a topic. When they are asking the question, they will take the time to honestly think through the answer. Real learning only happens when they think the thoughts for themselves. All I can do is act as a sort of tour guide.

So the n-th triangle number is just the sum of the first n numbers. Why are they called triangle numbers? Have a look at this picture:

The first 6 triangle numbers

In some future posts, all available in this blog’s Figurate Numbers category, I’ll show how we can put triangles and squares together to build new triangles and squares.  These pictures will translate directly to equations, or Arithmetic problems.  We’ll see how some tedious looking problem sets are really telling us stories about shapes.

Some other reasons triangle numbers are important

I like the fact that triangle numbers allow us to play some fun games with numbers, and provide a simple example of how Arithmetic can represent seemingly unrelated concepts like “shape”.  They are also valuable because they give us the simplest example of an arithmetic series, and once you know how to compute triangle numbers, it is pretty easy to figure out how to add any arithmetic progression (again, I’ll go into the details in a later post).

Once we know how to sum these series, we’ll be able to move into elementary Calculus and evaluate our first integrals.  Along the way, we’ll also find a way to test whether a number is a triangle number and develop a formula that tells us which triangle number it is.

These numbers give us a nice setting to introduce some real Mathematical thought in a fairly elementary way.  This is a theme I plan to come back to repeatedly on this blog.

In case your Geometry is a little rusty, the Pythagorean Theorem tells you how to compute the length of one side of a right triangle when you know the length of the other two. If we have a right triangle like this one:

then the Pythagorean Theorem states that .

Here is one way to see that it is true. Let’s take four of these triangles and arrange them like this:

Now we have made a large square, with sides of length , out of four of our triangles. We just have a little square “hole” in the middle.

A first pass

Let’s have a look at the area of all of these pieces. The area of a triangle is half of its base times its height, so the area of all four triangles put together is

The area of the large square is just , so we know that

Area of Square = Area of Triangles + Area of Hole

+ Area of Hole

Let’s look at that square hole. It’s side has length , so it’s area is just . This lets us write

Which is just what we were looking for. But we don’t have to be so quick to lean on our Algebra crutch here.

A “Tangram” proof

Actually you can just print out that square, cut out each of the pieces, and rearrange them into a new shape like this (click on the image for a clear view):

The shading will help you see that this new configuration is just a square with side next to a square with side (shaded). This is just the sort of thing you do when you play with tangrams: break shapes into smaller pieces and rearrange them to make different shapes. This is also the sort of argument that appears again and again in Euclid’s Elements.

Try this at home! Cut out the pieces (I made a template here), and cut out the squares (template here). Arrange the shapes yourself to see that .

Even pretty young kids can play these games and develop some important intuition, even if they don’t appreciate the importance of the results. I know I think that the Pythagorean Theorem is one of the most important non-trivial results in Mathematics. When I showed this to G, he said “Of course, I already knew how to do that when I was three” Then he started making his own designs with the pieces.

Extra Credit Puzzle

OK, I know this is old hat to some of you, so here are some meatier things to think about. This argument is very old. As David Joyce points out

The rule for computing the hypotenuse of a right triangle was well known in ancient China. It is used in the Zhou bi suan jing, a work on astronomy and mathematics compiled during the Han period, and in the later important mathematical work Jiu zhang suan shu [Nine Chapters] to solve right triangles.

The Zhou bi includes a very interesting diagram known as the “hypotenuse diagram.” This diagram may not have been in the original text but added by its primary commentator Zhao Shuang sometime in the third century C.E.

The hypotenuse diagram is just the picture we’ve been playing with throughout this post.

1. Why didn’t Euclid use this proof in The Elements? After all, Plato seemed to be aware of it (see Meno).
2. Turn this argument into a formal proof using only results from Euclid’s Book I. (Proposition 47 is off limits, of course.) Is that proof longer or shorter than Euclid’s Book I Proof?
3. What if you get to use results from Book II as well? (Hint: that rearrangement I made looks like it came straight out of Book II).

If you can answer those questions well, you’ll have a reasonable chance of passing my Geometry class .

If you want to see a menagerie of different proofs of this theorem, take a look at the Pythagorean Theorem and its many proofs at Cut the Knot.

Riemann -function

No, we won’t take on the Riemann Hypothesis, but I will try to convince you that understanding how the -function behaves is really the same as understanding prime numbers and how they are distributed. We’ll start this by proving a specific result, namely

In other words, the sum of the reciprocals of the primes diverges.

Here I’ll give the simplest proof I can think of, relying only on a little bit of Algebra II. If anyone can do better, please let me know! I’m not aiming for rigor here, although I’m happy to provide rigor on request.

Adding All the Numbers

I want to start by playing some games with multiplication and addition.

First, notice that

For the moment, don’t try to add the numbers. Just think of addition as a way to write a list of numbers. This example shows how we can use multiplication to take two short lists and make a longer list.
What if we want a 4 to show up in the list? We can just write

Now we are missing 5, so we fix it like this

We can keep going like this: multiply by (1 + 7) to put 7 in the list, multiply by (1 + 2 + 4 + 8 ) instead of (1 + 2 + 4) to get 8 in the list, multiply by (1 + 3 + 9) instead of (1 + 3) to put 9 in the list. Play around with it, and you’ll see that

We can keep going like this, and will hit a hole in our list every time we hit either (1) a new prime number, or (2) a power of a prime number that we’ve already seen. We know how to fill in those holes

1. When we hit a new prime number, $latex p$, multiply by
2. When we hit a power of a prime number that we’ve already seen, say , we will already have a term in our product that looks like , so just add to this term, giving you

If we keep going this way, we’ll put every number in our long list and no number will show up twice (this is another way to say that numbers can be uniquely factored into primes). We’ll end up with this interesting equation

Of course this is meaningless. Interesting, but meaningless. But interesting is good enough for me, so let’s charge forward.

In my first post in this series I introduced the Sigma notation for sums, so we didn’t have to write out all of those +-signs and ‘…’ marks. We can use that to make our formula a little more concise and precise here:

But we still have an infinite number of multiplications cluttering up the equation. We can use the Greek capital Pi, , just like we used Sigma before to take care of this. So, for example

is just a shorthand way to write

Using the Pi notation, we can write

Still meaningless, but it looks impressive!

Back to the zeta function

Now let’s make it meaningful. We weren’t interested in adding up whole numbers anyway. In our last post we found that when s > 1 we can define the Riemann zeta function

Well we can play the same sort of list-making games with the numbers that we did with the whole numbers. For example

And so on. Try it.

This happens because the function is a homomorphism: . [Excercise: Verify this.] If we repeat our argument from above, we’ll be able to write down a very fancy looking formula that actually means something

But wait a minute. Look at all of those sums on the left hand side — the ones that look like . These are just geometric series, and we know that this just equals ! So we can simplify the expression and write

This is called Euler’s product formula for the zeta function.

This is starting to look good. We’ve found a way to write the zeta function that only involves the prime numbers. And it is a neat expression, an analytic way to say that every number can be uniquely factored into primes. Any number that can’t be factored wouldn’t show up in our list-building exercises, and any number that can be factored two ways would have shown up in our list twice. I never proved that this can’t happen, so you might want to think about it a little more.

Turning products into sums

The problem is that we have an infinite product, and I had set out to study an infinite sum of primes. Luckily there is a function called the logarithm that turns multiplication into addition: . I’m going to use the natural logarithm because, well, it’s natural. (Unless you’re doing computer science, when it’s natural to let e = 2.) Applying logs gives us the equation

But it’s easy to check that (just look at ), so we can now write

Approximate, simplify, and control the error

Now as p gets big, the value is going to get really small. We know that , so we would expect to be really close to zero. If we knew how fast the logarithm function was changing near zero, we could get a pretty good estimate for these terms in the sum. Well here is a graph of the function and the function near .

It turns out that is a pretty good approximation. If we could just swap this function for the log function it would be great! We’d have

Which is just the sort of sum we wanted to study. This is why we used the natural logarithm instead of , say a base 10 or base 2 logarithm: the natural logarithm is the only one that is well approximated by a line with slope 1. If we used a different logarithm, we’d get some messy looking constants in our approximation.

Now we should make sure that our approximation is good enough!

To do that, let’s plot the error we make when we swap for and compare it to the function .

Notice that if x is close to 1, our error is much bigger than , but as long as , the error we make is certainly less than . For prime numbers p, is always going to be less than a half, so we can write

But now we know that because the second sum ranges over all of the numbers, not just the primes. We also know, from our last post, that

So we can write

And we have a pretty good idea how big our sum over the primes must be.

Now here is the fun part: , as we saw in our last post. This means that

This can only happen if is infinite.

QED

Earlier I said this means that there are “a lot” of primes — enough to make this sum go to infinity. In a later post I’ll make this more precise.

The harmonic series

Here is a sum that shows up frequently in Mathematics:

This is called the harmonic series.  I’ve promised that I’ll use this stuff to say some important things about prime numbers, but I keep putting off to a later post.  Here is a preview to keep you interested: This is just like , except now we are summing over all whole numbers, not just primes. If “a lot of numbers are prime”, then the difference shouldn’t be too great. If “very few numbers are prime”, then the difference should be large. So measuring the difference between these two sums is really the same as understanding the distribution of the prime numbers. More on that later, now let’s get to work.

I claim that the harmonic series diverges. It will keep growing and growing. To see why, let’s break it into chunks. The first chunk will be pretty small: it is just the first term, 1. The second chunk has two terms: . The next chunk has 4 terms: . The next chunk has 8 terms, then 16, and so on. Each chunk has twice as many terms as the one before it.

Now look at the size of the terms in each chunk. The first chunk has one term, and it has a value of 1. The second chunk has 2 terms — and and both of them are certainly bigger than . So the sum of terms in this chunk has to be bigger than .

The next chunk has 4 terms and they’re all bigger than , so the sum of terms in the next chunk must be bigger than .

The next chunk has 8 terms bigger than . And so on. Here is a little picture of the first few terms. The red bars show the values and the green boxes show the lower bounds.

The n-th chunk has terms, and they are all bigger than . This means that when we add up the terms in each chunk we get some number bigger than one half. But there are an infinite number of chunks! If we add an infinite number of times, of course the sum will keep growing and growing. It diverges.

And the harmonic series is even bigger:

So we can safely say that . The sum diverges.

This process of breaking a sum into manageable chunks, each one twice as big as the last, is called a dyadic decomposition.

An almost-harmonic series

The numbers get smaller and smaller, but they don’t get small fast enough to make the harmonic series converge. what if we made the terms smaller? Consider the series

We can play a similar game with this series, breaking the sum into chunks. Only this time we are going to show that the sum of terms in each chunk is smaller than some small number.

The first chunk is easy, it has one term and the sum is just one. In the next chunk, notice that each term is smaller than . There are two terms, so the sum for this chunk is less than .

For the third chunk, there are 4 terms, and each of them is smaller than so the sum of terms in this chunk is less than . For the fourth chunk, we find the sum is smaller than , the sum of terms in the fith chunk is smaller than and so on.

Putting these together we find that

This is just the geometric series we saw in the last post, and it converges to . So we know that

Not only does the sum converge, it is pretty small. The exact value of the sum was found by Leonhard Euler (it was called the Basel problem), and is .

We can also look at series that lie between this one and the harmonic series. Consider any number s > 1. We can look at the series

A slight variation of the argument I just gave shows that this sum converges as long as s > 1. (Exercise: [1] Prove this for s = 1.1. [2] Prove this for all s > 1.) So we can talk sensibly about this sum , and study the way it changes as changes.

is known as the Riemann zeta function. It is the function that lies at the heart of the Riemann Hypothesis — perhaps the most famous unsolved Math problem today. As we’ll start to see in the next post, if we can understand zeta, then we understand the primes.

If that sounds like it’s beyond the scope of your Calculus class, don’t worry. All you need are good Algebra skills and a bit of motivation.

Let’s start by looking at one of the simplest types of series around, the Geometric Series.

Some sums are finite: Geometric Series

When students first come across infinite series, many of them have trouble understanding how you could possibly add an infinite number of numbers together and get anything that makes sense. You can only add one new number at a time, how can you finish? Shouldn’t the answer be infinite? If you don’t wonder something like this, you may not have developed a healthy respect for the dangers of infinity.

It turns out that if we are careful, we can talk precisely about the “value” of infinite sums, even though we can never finish adding the terms. You may see this developed in a Calculus or undergraduate Analysis class. Until then, this example — a variant of Zeno’s Paradox — will give you the basic idea.

Imagine you are crossing a street. Of course you could just walk across and be done with it. Or you could cross the street like this:

1. Cross half way [distance traveled: 1/2, distance remaining: 1/2]
2. Cross half of the remaining distance. [distance traveled: 1/2 + 1/4, distance remaining: 1/4]
3. Cross half of the remaining distance. [distance traveled: 1/2 + 1/4 + 1/8, distance remaining: 1/8]
4. Cross half of the remaining distance. [distance traveled: 1/2 + 1/4 + 1/8 + 1/16, distance remaining: 1/16]
5. And so on

This process never stops, but it keeps getting you closer to the end of the street. In fact it will get you as close as you want to the other side of the street and it doesn’t take you anywhere else. We can safely say that after you do all of this, you’ve crossed exactly one street:

This is an example of a geometric series. To get a general geometric series, pick any number . Now we can look at the sum

If then the series is , which obviously just keeps getting bigger. If the problem just gets worse. (Exercise: what happens when ?)

But if then this sum will get closer and closer to a number that we will call the “sum of the series”. We can figure out exactly what this number is. If we call it then:

So , or

All these long sums get tedious to write, so we will start using some shorthand. We will use a Greek capital Sigma, $\Sigma$, to denote a sum, like this:

(Remember, ! ) For an infinite series, we’ll need to write

It looks fancy, but it’s just a way to save some writing and make things more precise. Whenever I put those “…” marks in, I was trusting that you’d know what was supposed to come next. That will cause trouble down the road, and our new notation avoids it. Have a look here if you want a bit more detail.

So let’s get back to our street crossing experiment. At each step, we were going half as far as we had in the previous step. So . As we crossed the street, we crossed half, then a fourth, then and eighth, and so on. So we can write the number of streets we crossed like this:

This almost looks like the geometric series in our formula above, but it starts with one-half, not one. We’ll fix that by adding one to both sides:

So

Whew! I’d have been a little worried otherwise.

When I write about prime numbers in my next post, we’ll use these geometric series a lot. It’s amazing how many places they pop up.