Posted by Back in 2003, I was a college freshman sitting in my first college math class – Honors Calculus I. On what was probably the second or third day of class, the professor gave us a surprise quiz. It was something like: “Give the formal statement of the principle of induction”. It was my first graded assignment of my college career, and like most of the class I got a 0 on it.
Which was the professor’s point – he had gone over it in great detail previously and was baptizing us by fire into the world of mathematical rigor. We didn’t yet understand that mathematics both requires great attention to formal detail while simultaneously requiring creativity of thought that can’t often be reduced to simple algorithms. And so we learned to pay attention to those careful definitions and to see the logical problems that followed from sloppy definitions. It ended up being one of the best classes I’ve ever taken.
The principle of induction is a rather interesting one. It works like this:
Let’s say you want to prove that all the dominoes are going to fall. One way to do this would be to prove that the fall of one causes the fall of the next, and that the first domino falls. Those two statements combined prove that all the dominoes will fall.
Mathematical induction works much the same way. If we have a statement that purports to be true for all natural numbers n, we can proceed by analogy to the domino problem in attempting to prove that statement. We have to show that given a specific natural number k that satisfies the statement, the natural number k + 1 also satisfies the statement. Then we have to show that the natural number 1 satisfies the statement. Because then k = 1 works, which proves that k = 2 works, which proves that k = 3 works, and so on.
So let’s try this. Let’s show that this sum rule is true for all n:
The right side of that equation is a function of n, which we’ll go ahead and give it the official title of this week’s Sunday Function. We don’t know that it works for all n. But for the sake of argument, let’s say that it works for some specific k. We use the letter k instead of n because n is any number while we’re using k to denote a specific number for which this statement is true. There may or may not actually be one. The first half of the proof is to show that the truth of k working implies that k+1 also works. The second half is to show that there is in fact some working k. So assuming k works:
We know that this must also be true:
Here we just took the k equation and added k + 1 to the left side. Then we substituted in k+1 on the right side. So the resulting equation we just wrote ought to be true, if in fact “works for k” implies “works for k + 1″.
We just multiply everything out to check. When we do this, we get:
Which is true. Thus k really does imply k+1. So, for instance, if that sum equation works for k = 23, then it works for k = 24.
So now we have to establish that there is in fact some k that it works for. There might not be. Because the k -> k+1 step is usually the difficult one, sometimes people forget that at some point you do have to show that k = 1 actually does work. That one domino would knock over the next doesn’t prove squat if the first one never actually falls.
Does this particular sum rule work for k = 1? It’s pretty easy to check. Letting k = 1 is just to say that 1 = 1(1+1)/2, which is in fact true. Since k = 1 works and each k implies the next, the sum rule works for all natural numbers.
If you want to compute 1 + 2 + 3 + … + 384,924,734 all you have to do is one multiplication and one division and you’ll see the answer is 74,083,525,614,947,745. Which is a heck of a lot easier than adding up a few hundred million integers.
Induction isn’t the only way to prove this, or even the easiest. But it is one of the most versatile proof techniques in mathematics and this is a nice clean example of how it works.
June 6, 2010
June 6, 2010
June 6, 2010
June 6, 2010
June 7, 2010
June 8, 2010
June 8, 2010
June 9, 2010