Proof by induction is a very powerful weapon in the number theorist's armory. The idea behind it, though, is a very simple one. Given a conjecture that we wish to prove, we start off by showing that, if it is true for some number n, then it must also be true for the number n + 1. The second and final stage is to show that the conjecture is true for a given, preferably low, n. If we can do both, then we have effectively shown that the theorem is true for all n greater than or equal to the low value of n for which we proved a specific case. Typically, the second stage involves proving that the conjecture is true for n = 0 or n = 1. (If you prefer, of course, you can do these two steps the other way around. It doesn't matter, as long as you do them both!)

The canonical example of proof by induction is the formula for summation of integers between 1 and n. Before we get going, though, I can't resist relating a (probably true) story on the history of summation.

Karl Friedrich Gauss (1777 - 1855) was one of the greatest mathematicians who ever lived. He was responsible for a considerable number of mathematical advances. The story is often told of his confounding his mathematics teacher whilst still at a very tender age. Teachers the world over will sympathise when I explain that this particular teacher just wanted a quiet morning. Perhaps he had a lot of marking to do, or perhaps he was still recovering from a cheerful night in the tavern. We don't know. But he can perhaps be forgiven for believing that he could occupy his class for a good part of the morning by asking them to add up all the integers from 1 to 100.

Within just a few seconds, however, Gauss had found the correct answer. He had probably reasoned as follows:

"The numbers from 1 to 100 can be split into pairs, {1, 100}, {2, 99}, {3, 98}, etc. There are 50 such pairs, and each adds up to 101. So the answer is 50 × 101, which is 5050."

So much for a quiet morning. He should have asked them to prove Fermat's Last Theorem!

We can generalise Gauss's technique into a formula. Let S(n) be the sum of all the integers between 1 and n (inclusive of both 1 and n). Then S(n) = n(n + 1) / 2.

But can we prove it?

Let's start by showing that, if it is true for some number n, then it must also be true for the following number, n + 1. (That's a 1, and not the letter between k and m, which is not used as a symbol for a variable, anywhere on this page.)

So we start by assuming that the sum of numbers between 1 and n (which we represent as S(n) can be truly represented by the formula S(n) = n(n + 1) / 2

Secondly, we observe that the sum of numbers between 1 and n + 1 is clearly equal to the sum of the above formula and n + 1. (If this isn't clear to you, consider the simple case n = 2: 1 + 2 + 3 is equal to (1 + 2) + 3.)

Therefore, S(n + 1) = n(n + 1) / 2 + n + 1

We can simplify this formula a little:

S(n + 1) = n(n + 1) / 2 + 2(n + 1) / 2

S(n + 1) = (n(n + 1) + 2(n + 1)) / 2

S(n + 1) = (n + 2)(n + 1) / 2

We know that this is correct (provided our original assumption is correct). So now let's plug n + 1 into the function.

We introduce a second quantity, m, not through necessity but because I'm striving for clarity; so let m = n + 1

Therefore S(m) = m(m + 1) / 2

Plugging n + 1 back into the equation in place of m, we get:

S(n + 1) = (n + 1)(n + 1 + 1) / 2

Simplifying (by combining 1 + 1 into 2), we get:

S(n + 1) = (n + 1)(n + 2) / 2

This is identical to our previous derivation. So we have shown that, if S(n) = n(n + 1) / 2 is true for n, then it must also be true for n + 1.

Now comes the sneaky bit. Let's add up all the numbers between 1 and 1. Well, it's 1, obviously. Does the equation work for n = 1? Does n(n + 1) / 2 give us the answer 1?

Well, 1(1 + 1) / 2 = 1 × 2 / 2 = 2 / 2 = 1. So it does work.

Since we have already shown that, if it is true for n, it must also be true for n + 1, and since we have shown that it is true for n = 1, then it must also be true for n = 2. And since it's true for n = 2, it must also be true for n = 3. And so on, to infinity.

We must be careful. Just because we have shown that it is true for all values of n greater than or equal to our base case, it does not follow that it is true for numbers below our base case. That's why we choose the lowest base case that makes sense. We could not reasonably expect the equation to tell us what number we get if we set n to 0, or to -1. And indeed this reflects the reality of the meaning of the equation. After all, if we start from 1 and keep adding 1 to it, we aren't going to reach 0, or -1, ever.

The sum formula is the classic example of proof by induction, but I'd also like to present a second proof, which is perhaps less well known. (Indeed, as far as I can tell, I'm the first person ever to prove the following theorem in the following way.)

Consider the series 1, 2, 4, 8, 16... It's quite obvious that the next term in the series is 32, but of course what is obvious doesn't necessarily agree with what is correct. If the series is a straight rendition of 2ⁿ, then the prediction of 32 is correct. But could there be another series that starts in that way, but which has a different next term?

Consider a circle with n dots around its circumference (in our example image, n = 5), with each dot joined to every other dot by a straight line:

The idea is to count the number of regions into which the circle has been divided. Clearly, if there's just one dot, then no lines divide the circle, so there's just one region. Equally clearly, if there are two dots, then just one line divides the circle, so it's divided into two regions.

Once we hit three dots, though, we actually get a triangle of dividing lines, with each side of the triangle bounding a region (giving us three), and with the inside of the triangle counting as a fourth. So the relationship is not a simple linear one. By the time we have five dots (see above), the number of regions is 16. In our next image, however, the apparently obvious relationship starts to break down:

If you count them carefully, you will see that there are not 32 regions, but only 31.

In general, it turns out that there are (n⁴ - 6n³ + 23n² - 18n + 24) / 24 regions in a circle with n dots.

I don't seek to prove this! What I do hope to demonstrate, however, is that this equation always yields an integer result, despite the division by 24. (Anyone seeking to prove the above equation might well start by first establishing this result.)

My plan of attack is, of course, a proof by induction. Now, just to get it out of the way, let's start off by proving that the expression does indeed yield a value divisible by 24, when n = 1. We have 1⁴ - 6×1³ + 23×1² - 18×1 + 24, which is equal to 1 - 6 + 23 - 18 + 24, which is equal to (1 + 23) - (6 + 18) + 24, which is equal to 24 - 24 + 24, which is equal to 24. And clearly 24 is divisible by 24. So the equation does indeed yield an integer result for n = 1.

Let us continue by showing that, if (n⁴ - 6n³ + 23n² - 18n + 24) is evenly divisible by 24, then so is ((n + 1)⁴ - 6(n + 1)³ + 23(n + 1)² - 18(n + 1) + 24).

Firstly, then, we need to expand the expression for n + 1. It comes out as

n⁴ + 4n³ + 6n² + 4n + 1 - 6(n³ + 3n² + 3n + 1) + 23(n² + 2n + 1) - 18(n + 1) + 24, which expands to:

n⁴ + 4n³ + 6n² + 4n + 1 - 6n³ - 18n² - 18n - 6 + 23n² + 46n + 23 - 18n - 18 + 24.

Now before we get too excited about gathering like terms, let's see if we can't do something a little sneaky. Consider the following rearrangement of the above expression:

n⁴ - 6n³ + 23n² - 18n + 24 + 4n³ + 6n² + 4n + 1 - 18n² - 6 + 46n + 23 - 18n - 18

The first five terms of this expression are the same as for the original expression. Now, remember that we're trying to show that, if the expression yields a result divisible by 24 for a given n, it also yields a result divisible by 24 for n + 1. So we can take it as read that n⁴ - 6n³ + 23n² - 18n + 24 is divisible by 24, and just focus on the remaining part of the expression, i.e.

4n³ + 6n² + 4n + 1 - 18n² - 6 + 46n + 23 - 18n - 18.

Now we can gather like terms. This gives us

which simplifies to:

4n³ - 12n² + 32n

with all the constants nicely cancelling each other out. We are beguilingly close to a proof. We now have everything we need except a proof that 4n³ - 12n² + 32n is divisible by 24. If it is, then we're done.

So how do we prove that the above expression is divisible by 24? Well, the obvious attack is -- induction! After all, the expression is simpler than the first expression, and so we can reasonably expect that a further inductive attack will yield either a proof or, at worst, a simpler expression still. Let's do it.

Firstly, let's show that the expression yields a result divisible by 24 if n = 1. This is easy: if n = 1 then all the power terms reduce to 1, giving us 4 - 12 + 32, which is -8 + 32, which is 24, and that's clearly divisible by 24. So now we do the induction part. If the expression yields an integer result for n, then does it yield an integer result for n + 1? We need to prove that:

4(n + 1)³ - 12(n + 1)² + 32(n + 1)

is divisible by 24. Expanding it, we get:

4(n³ + 3n² + 3n + 1) - 12(n² + 2n + 1) + 32n + 32

and expanding that gives

4n³ + 12n² + 12n + 4 - 12n² -24n - 12 + 32n + 32

which we can rearrange as

4n³ - 12n² + 32n + 12n² + 12n + 4 - 24n + 20

We know the first three terms are divisible by 24, so we now need only prove that

12n² + 12n + 4 - 24n + 20

-- which we can simplify to

12n² - 12n + 24

-- is divisible by 24. Again, we can prove this by induction. Firstly, we show that it's true for n = 1, which is trivial because 12 - 12 + 24 equals 24, which is indeed divisible by 24. Now we substitute n + 1 for n and expand.

12(n + 1)² - 12(n + 1) + 24

is equal to

12(n² + 2n + 1) - 12n - 12 + 24

which expands to

12n² + 24n + 12 - 12n - 12 + 24

which can be rearranged as

12n² - 12n + 24 + 24n + 12 - 12

We know the first three terms are divisible by 24, so we need only prove that 24n + 12 - 12 is divisible by 24. Since 12 - 12 is 0, this simplifies to 24n, which is exactly divisible by 24.

And that's it. Every link in the chain is now complete, and we can state with complete assurance that (n⁴ - 6n³ + 23n² - 18n + 24) / 24 always yields an integer result. QED.