Is Mathematical Induction the Key to Understanding Finite and Infinite Concepts?

[matqkks]

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real life applications of induction?

 

[lurflurf]

Dominoes or a ladder or stairs are good analogies. Also counting or any example of a unbounded finite process. So explain how do we know we can count to n? Suppose a lock has an integer combination we are sure to open it eventually. Can we weigh an elephant with small pebbles? The Euclidean algorithm will terminate. Pose it not so much as handling all integers (which is true but confusing) but a way to build up to handle some particular large integer.

 

[dkotschessaa]

Is showing the equivalence of the well ordering principal and induction too abstract for your intended audience? The WOP seems so very obvious and easy to understand, but it's very interesting to look at all it's implications. Maybe there's a way you can de-abstract the WOP, show its equivalence to induction...

Also the peano axioms (in a basic form like here http://mathworld.wolfram.com/PeanosAxioms.html) are very easy to swallow and equivalent to induction.

That of course is the abstract approach. But maybe it could help?

 

[SteveL27]

Is showing the equivalence of the well ordering principal and induction too abstract for your intended audience?

At the end of the (mathematical) day, the only reason induction is true is because we assume an axiom that says it's true. There are (as far as we know) no infinite sets in the universe. The natural numbers 1, 2, 3, ... along with the induction principle, exist only because

* The Peano axioms (PA) say they do; and

* The Axiom of Infinity of ZF provides a model of PA.

Absent those assumptions, there's no reason to "believe" in infinitary processes. It's intellectually honest to explain to students that induction is "true" because it's true about the abstract mental model of the natural numbers that we assume in order to do mathematics. That's really the only reason.

Induction is not "true" in the same sense, that, say, the law of gravity is true. You can drop a rock from a height and show that general relativity explains its gravitational acceleration to within a dozen decimal places.

Induction has no such justification. Induction is "true" only because we agree that PA is a correct characterization of our mental model of the counting numbers. Ultimately this is a matter for philosophers.

I wonder what would happen if we were honest with students about these kinds of things.

 

[dkotschessaa]

Nice points Steve.

 

[Tobias Funke]

At the end of the (mathematical) day, the only reason induction is true is because we assume an axiom that says it's true. There are (as far as we know) no infinite sets in the universe. The natural numbers 1, 2, 3, ... along with the induction principle, exist only because

* The Peano axioms (PA) say they do; and

* The Axiom of Infinity of ZF provides a model of PA.

Absent those assumptions, there's no reason to "believe" in infinitary processes. It's intellectually honest to explain to students that induction is "true" because it's true about the abstract mental model of the natural numbers that we assume in order to do mathematics. That's really the only reason.

Induction is not "true" in the same sense, that, say, the law of gravity is true. You can drop a rock from a height and show that general relativity explains its gravitational acceleration to within a dozen decimal places.

Induction has no such justification. Induction is "true" only because we agree that PA is a correct characterization of our mental model of the counting numbers. Ultimately this is a matter for philosophers.

I wonder what would happen if we were honest with students about these kinds of things.

This may be true, and I'll leave such considerations to the philosophers, but is it actually helpful for any student who doesn't "believe in" induction? I think it's too close to the "math is just a game played under certain rules" point of view, which I often see here in somewhat extreme forms. For example, someone will ask why 5 times 12 equals 12 times 5 in such a way that it's clear that this person isn't very mathematically sophisticated, and the best explanation is to draw a 5 by 12 rectangle or 5 rows of 12 dots, etc., and then view this in two different ways. Instead, too often the answer is simply something like "by the axiom of commutativity for rings".

I think your answer is similar; it's suitable for advanced students who pretty much already understand induction in terms of dominoes or ladders, but seems to invert cause and effect and is in some sense a non-answer. Isn't it more honest to say that the axiom of induction is chosen because induction is "true", meaning roughly "intuitively clear", instead of the other way around? Then we're back at square one: why do we accept this axiom?

That may have been too wordy and I didn't mean to pick on your answer for two paragraphs (I actually think it's a pretty good answer), I'm just not sure if it's appropriate for beginners. I agree with lurflurf about not trying to consider the infinite sets as a whole, but by "building up" to a number as large as we want (something like the difference between actual and potential infinity). After all, mathematicians who would have outright rejected modern theories of infinite sets were using induction hundreds of years ago, so that doesn't seem to be a huge stumbling block.

I can't think of any amazing examples to convince them now, but I always thought the L-shaped tiling problem was interesting. Also prime number factorization, although that's strong induction (which I think I remember being equivalent to regular induction anyway). Both are described http://www.stanford.edu/class/cs103a/handouts/42%20Mathematical%20Induction.pdf.

I actually don't like most of the standard examples using induction, like 1^2+2^2+...+n^2=whatever, because there are usually better and more interesting ways of doing them.

 

[SteveL27]

This may be true, and I'll leave such considerations to the philosophers, but is it actually helpful for any student who doesn't "believe in" induction?

Oh of course you're right. I was not seriously suggesting that we try to explain this sophisticated point of view to beginners. Or if I did believe it for a moment, it didn't last long. I visualized a room full of students asking, "Will this be on the test?"

The way I explain induction to a beginner is to say, "If P is true for zero; and it's true for n + 1 whenever it's true for n; then it P must be true for all counting numbers. And if you don't believe me ... name the first number where P is false!"

I think that last part makes them visualize the dominos falling. I know it does for me.

 

[mathwonk]

by the way, as an amusing comment, as an abstract principle WO is actually much stronger than induction, i.e. they are not equivalent. They are equivalent for the natural numbers of course but not in general. Think about the well ordered set consisting of the natural numbers but ordered so that all even numbers are larger than all odd numbers. then the usual proof by induction (the truth of P for any element implies P also holds for the "next larger" element) only proves a result for the odd integers, but WO would prove it for the whole set.

A proof by induction is only valid for WO sets in which every element has a predecessor, as in the natural numbers.

 

[Stephen Tashi]

Show the students examples that demonstrate the distinction between "true for any finite number however large" and "true for an infinite number". (e.g. for any finite set of numbers, there is a maximum). If the students see that the power of induction is limited, they are more likely to believe it.

 

[D H]

Show the students examples that demonstrate the distinction between "true for any finite number however large" and "true for an infinite number". (e.g. for any finite set of numbers, there is a maximum). If the students see that the power of induction is limited, they are more likely to believe it.

Example: Since the union of two closed sets is itself a closed set, the union of any finite number of closed sets is a closed set by induction. This obviously is not necessarily true for the union of an infinite number of closed sets.

I think what Stephen is getting at is that "Mathematical induction affords, more than anything else, the essential characteristic by which the finite is distinguished from the infinite." (Bertrand Russel)