Built on Facts

Sunday Function

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:

i-fcc309b3702a945b09a13d9fbbb66533-dominos.png

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:

i-d4bb9fe09d6b78eb832985821d8a307f-1.png

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:

i-88516ca505d84f969b7ab15a965c3fb3-2.png

We know that this must also be true:

i-d18063683dcc0d42b9be45451a84d1e3-3.png

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:

i-8d7070ce28f0af28047c7a5fb8246d53-4.png

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.

Comments

  1. #1 Uncle Al
    June 6, 2010

    31 prime,
    331 prime,
    3331 prime,
    33331 prime,
    333331 prime,
    3333331 prime,
    33333331 prime,

    k^2 + k + 41
    generates prime numbers: k = 1,2,3… 10… 20… 30… 40…

    |(1/4)(k^5 – 133k^4 + 6729k^3 – 158379k^2 + 1720294k – 6823316)|
    generates more prime numbers: k = 1,2,3… 10… 20… 30… 40… 50…

    Perhaps mathematical induction is also subject to Lenz’ law.

    http://www.prime-numbers.org/

  2. #2 joemac53
    June 6, 2010

    My pre-cal students get this version:

    You claim a rule to be true. Show it works for n=1 (this satisfies the legal requirement, but you should probably check for n=2 also)

    Show the consequence to the rule if you go to the (n+1)th term.

    Now do the algebra, that is assume your rule works for the first n terms and apply the next term ((n+1)th term)

    If your algebra matches the consequence to the rule, then your rule is good.

    The students have no problem going to the next term. They seem to have a hard time remembering that they must assume the rule is good for the first n terms when they have to do some algebra.

    I probably won’t do this again, as I am retiring after 35 years teaching math and physics (the best teaching job you can have).

    Keep up the good work in your posts. I’ll still be paying attention.

  3. #3 joemac53
    June 6, 2010

    By the way, the sum of the integers 1 to n is called the “Baby Gauss Rule” after that story about Gauss as a young student. Students are required to know it as (n/2)(first + last)

  4. #4 Nemo
    June 6, 2010

    I learned it as:

    Prove the statement is true for 1.

    Given that the statement is true for all k from 1 through n, prove it is true for n+1.

    Assuming the statement for all k from 1 through n is stronger than just assuming it for n, and sometimes this stronger assumption is helpful (or necessary) to complete the induction. Also, this formulation morphs more naturally into “transfinite induction”, if you are into that sort of thing.

  5. #5 Snarkyxanf
    June 6, 2010

    (\forall n . P(n) -> P(n+1)) -> P(0) -> \forall n . P(n)

    That’s a pretty mean quiz for freshmen, actually.

  6. #6 Noumenon
    June 7, 2010

    Off-topic request, just because I know you know physics:

    I keep hearing people say that cruise control is dangerous because it keeps you from taking your foot off the gas the instant you spot trouble. I never believed this, because if you do take your foot off the gas, it takes hundreds of feet to slow down even 5 miles an hour. My father says to imagine the engine is a big truck pushing your car along, and you can see it would help if the truck stopped pushing you before you hit something. I said that’s only because the truck’s mass gives you more momentum, and the engine is different. What do you think?

  7. #7 Paul Murray
    June 8, 2010

    Of course, the rule of induction is itself inductive. One of those Godel statements, perhaps. It becomes obvious when you try to generalise it. The rule becomes:
    if P is known to hold for a subset of cases,
    and P(a) -> P(b) where b=foo bar (a),
    and (insert handwave here) this would cover all possible cases,
    then P is true for all possible cases.

    The handwave is the problem. How do we know that this business of adding 1 to k will eventually cover all possible cases? By induction.

  8. #8 Annonymous
    June 8, 2010

    The set of natural numbers is defined as the smallest set closed
    under the successor operation. To be precise the set of natural numbers is defined to be the intersection of all sets closed under the successor operation. Thus the Principle of Induction follows for the set of natural numbers from it’s definition.
    To be sure, to make this work one needs to know that at least one set closed under the successor operation exists. This is the role of the Axiom of Infinity in the Zermelo-Fraenkel Axioms.
    The usual form of the Axiom of Infinity simply states the
    existence of a set closed under the successor operation. In Levy’s book on set theory he shows that this form of the Axiom of Infinity can be deduced from a less specific form which merely asserts that some infinite set exists.

  9. #9 Annonymous
    June 8, 2010

    In the above comment I should have said that the set of natural numbers is defined to the intersection of all non-empty sets closed under the successor operation. Also the
    usual form of the Axiom of Infinity states the existence of
    a non-empty set closed under the successor operation.
    Without the Axiom of Infinity or some stronger axiom such as
    assuming the existence of Grothendieck Universes we can define the set of natural numbers and establish it’s inductive nature but we can’t show that it is non-empty.

  10. #10 ScentOfViolets
    June 9, 2010

    Of course, the rule of induction is itself inductive. One of those Godel statements, perhaps. It becomes obvious when you try to generalise it. The rule becomes:
    if P is known to hold for a subset of cases,
    and P(a) -> P(b) where b=foo bar (a),
    and (insert handwave here) this would cover all possible cases,
    then P is true for all possible cases.

    Actually, this comes from an axiom called the well-ordering principle: every subset of the natural numbers has a least element. To prove induction, you assume that it’s false, then look at the (nonempty) set of numbers for which the statement is false and note that it has a least element. The rest follows by contradiction.

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.