Subsection 8.10.4 Induction When the Objects Don’t Look Like Numbers
Mathematical induction works when there’s the notion of a first thing, a well-defined next thing, and so forth. The domain in which that’s the most natural way to look at things is the integers. The base case is typically 0 or 1. Then, for any integer n, the “next” one is its successor, i.e., n+1.
But mathematical induction can also be useful in other kinds of domains. Often the reason it’s useful is that we can assign integers in some natural way to the objects we’ve got. For example, maybe they have size or age or position in a stack or list.
Consider the stack of paper plates. Suppose that I want to prove that, no matter how tall the stack, all the plates will fly away. You might come back and say, “Surely not. That stack is way too heavy to be blown away.” But, if I can get you to agree that, yes, a single plate can easily be blown away, then I can prove, by induction, that all of them can.
To do this, we need two premises about the plates. (We didn’t usually need to add premises when proving things about numbers or about geometry because we assumed all of the ones that we already had.) But now we need two:
[1] The top plate will blow away.
[2] When the top plate blows away, the next plate becomes the top one.
Number each plate, starting from the top, with the positive integers. Number the top plate 1.
Claim to be proved: n (Platen will blow away)
Base case: Plate1 will blow away. This is so by premise [1].
Induction step: We must prove:
n ((Platen will blow away) (Platen+1 will blow away))The proof is straightforward. As soon as Platen blows away, Platen+1 becomes the top plate (by premise [2]). But then, by premise [1], it too, will blow away.
So, by the Principle of Mathematical Induction, all plates will blow away.
Nifty Aside
A stack of paper plates is a physical thing. Now imagine a stack or list or set that is represented in a computer. For example, the ordered list of students wanting to sign up for a class that’s full. Or the set of employees for whom paychecks need to be issued. Programs that deal with such data structures generally do so by processing one element at a time. But we want to be able to prove that, eventually, all the elements will be correctly processed. To do that, we often use induction proofs that look very similar to the one we just did for the paper plates.