31-circle-cross-blue-pattern.jpg

Homepage

Math and Life

Inducting Piles of Sand

Take a pile of sand.1

pile of sand.jpg

Is it a pile of sand?

Of course. (duh)

Now add one grain of sand to this pile. Is it still a pile?

Yes, adding a single grain of sand to any pile of sand, yields a pile of sand.

Therefore, I claim, if you can add any number of grains of sand to a pile of sand, you get another pile of sand. It is proven.


It may seem like that proof is build on sand, but it’s actually quite solid. This method of proof is called mathematical induction (as distinct from philosophical induction).

Most mathematical statements, like “the sum of the squares of the legs of a right triangle is the square of its hypotenuse” only needs to be proven once. You prove it, and say “ta-da!” then you’re done.

But some problems, like the unfaithful husbands from the last blog post, don’t lend themselves well to “ta-da!”-styled proofs.

For instance, the sum of the first n natural numbers2 is

1.PNG

How would you go about proving this?

You might start by trying a couple numbers:

2.PNG

So far, all of these cases work. That might be enough to convince you that this equation holds true, but it doesn’t make mathematicians happy. There is a history of conjectures being disproved with massive counterexamples, so we really shouldn’t be jumping to conclusions.

The goal here is to prove that this equation holds for all natural numbers. It’s impossible to test every case (as there are infinitely many), so we have to do something clever.


Let’s assume, just for the sake of argument, that our formula holds for case k. Here, k represents any natural number. So, by assumption…

3.PNG

Now I’ll ask what might seem like a weird question now, but will make sense later: Does this formula also hold for the number k+1? Symbolically…

4.PNG

From our assumption, the sum of the first k integers is k(k+1)/2, so we can replace the 1+2+3+...+k with k(k+1)/2:

5.PNG

On the left hand side, we can find a common denominator and simplify:

6.PNG

This last step3 is clearly correct, so I’ve removed the question mark.

How should we interpret this result? Well, we started with an assumption, so we can’t claim this is always true (or at least not yet). What we can say is that IF the our assumption is true, then our conclusion is also true.

In this case, we say “If the formula holds for some natural number, k, then it also holds for the next natural number”

Take a second to fully digest that


So why is this significant?

We know the formula works for n = 1, as

7.PNG

“If the formula holds for some natural number, k, then it also holds for the next natural number.”

1 is a natural number, so say k = 1. Because we know the formula holds for 1, it also must hold for the next natural number: 2.  

Now say that k = 2. Because we know the formula holds for 2, it must also hold for the next natural number: 3.  

Now say that k = 3. Because we know the formula holds for 3, it must also hold for the next natural number: 4.  

And on and on and on, each number a domino in a never-ending chain.


This process of mathematical induction can be split into two steps:

  1. Prove the base case. (in our example, n = 1)
  2. Assume that one case is true, and prove that the next4 case is true.

If you manage to do both these things, congratulations! You have completed a proof by mathematical induction.


1 s in S, S = { x | x is a pile of sand}

2Ok, yes there are some “ta-da!” proofs of this formula, but this is the “hello world” of induction, so here we are

3The last step is done by factoring out a (k+1) from both terms in the numerator

4One itty-bitty requirement here: the notion of “next” must always be defined.

image sources

Noah CaplingerproofComment