Subsection 8.8.4 Visualizing Mathematical Induction
Suppose that we have a set S about which we want to prove some property P. Further suppose that the elements of S can be arranged in order such that:
There is a smallest (first) element, and
Every element, except possibly a final one, has a unique successor (i.e., next element)
Notice that we do not require that S be finite, although it may be.
For example, the positive integers satisfy conditions [A] and [B]:
\(1 2 3 4 5 \cdots \)
The smallest positive integer is 1. And every positive integer has a unique successor, which we can compute simply by adding 1.
Then we can prove that every element of S satisfies P if we can show two things:
The smallest (first) element satisfies P, and
If any element satisfies P, so does its successor.
To visualize this, think about a man climbing an infinite ladder. Suppose that we know that he can step onto the first rung of the ladder. And we know that, whatever rung he’s standing on, he can always reach the next one (simply by stepping up to it). Then we know that he can reach any arbitrary rung. He just needs to climb the ladder one rung at a time.
Let’s call the informal technique that we’ve just described the ladder method (or the “flu shot method” if you prefer).
Exercises Exercises
1.
Starzzz is a hopelessly popular club. Outside the door the line is huge and getting longer every minute. It is, however, a perfect line – the bouncers see to that. Suppose that we want to prove that, eventually, everyone in the line will get the word that the star act has started. Is it possible that I could use the ladder method? (Hint: See if you can draw a ladder-like structure to describe the problem.)
Yes. I could start with the person at the front of the line. He would be able to hear the act start. I could define the successor of someone to be the person behind him/her in line. Then I could use the ladder method if I could show that anyone who knows about the act will pass the word to their successor.
No. The ladder method won’t work because there’s no reasonable first element.
No. The ladder method won’t work because there’s no reasonable definition of successor.
No. The ladder method surely won’t work because there’s no way we’ll be able to show that anyone who knows about the act can pass the word on to their successor.
Correct answer is A.
Explanation: The ladder method could probably work here. There’s a well-defined first element. There’s a clear way to specify who someone’s successor is. And it seems reasonable that we can show that if someone knows about the act then they can simply turn around and tell the next person.
2.
Consider the problem of proving that, no matter how far back I trace in a family tree, everyone has some property P. Is it possible that I can use the ladder method? (Hint: See if you can draw a ladder-like structure to describe the problem.)
Yes. I could start with a current member of the family. I’d have to be able show that P holds for that person. Then I could define the successor of someone to be their parent. Then I could use the ladder method if I could show that, if P holds of some person x, then P must also hold of their parent.
No. The ladder method won’t work because there’s no first element that I could start with.
No. The ladder method won’t work because there’s no reasonable way to define the unique successor of someone.
Correct answer is C.
3.
Consider the problem of proving that, no matter how far back I trace in a family tree, everyone’s mitochrondrial DNA has some property P. Is it possible that I can use the ladder method? (Hint: Assuming no mutations, which we’ll do, how is mitochrondrial DNA inherited? Once you know the answer to that question, see if you can draw a ladder-like structure to describe the problem.)
Yes. I could start with a current member of the family. I’d have to be able show that P holds for that person. I could define the successor of someone to be his or her mother. Then I could use the ladder method if I could show that, if P holds of some person x, then P must also hold of their mother.
No. The ladder method won’t work because there’s no first element that I could start with.
No. The ladder method won’t work because there’s no reasonable way to define the successor of someone.
Correct answer is A.
Explanation: I can start with a current member of the family. I can define successor to be mother. Now people are arranged in a straight line since everyone has exactly one mother. So I could use the ladder method if I could show that, if P holds of some person x, then P must also hold of their mother.