Mathematical Induction

The principle of mathematical induction is a topic that our textbook unfortunately skips over. It is used when we want to prove a rule that applies to positive integers. Often, it is the argument that is needed when you want to say, "See! It works the same way for this case and that case, so the pattern will just keep repeating." But to say that a pattern keeps repeating is exactly what we should attempt to make more precise.

The natural numbers are the set of all positive integers: 1, 2, 3, 4, .... It is the dot-dot-dot that creates the problem. Using "..." attempts to tell us that the pattern continues. But what exactly is the pattern? For the natural numbers, the pattern is that you just add one to the previous number. So here is one way of describing the natural numbers, and it is what motivates the principle of mathematical induction.

• 1 is in the set
• For every number that is in the set, call it n, we also have n+1 in the set.

We could restate this using an implication:

• 1 is in the set
• If n is in the set, then (n+1) is in the set.

And that is what we do for all applications of mathematical induction. We provide a starting point (such as 1 is in the set). Then we establish an implication that if a statement is true for one value (n is in the set), then it must also be that the statement is true for the next value (n+1 is in the set).

Here is an example from our past that should have used induction.

Theorem: xⁿ is continuous for n=1, 2, 3, ....

Scratchwork:
Before proving this statement, we should think how we might attempt this without induction. Well, f(x) is really a product xⁿ= x x x ... x, where there are n factors of x. (See how the "..." allows us to hand-wave our notation?) Well, we know that the limit of each factor x will just go to the value c, so the limit must be lim_{x → c} f(x) = cⁿ. That use of "..." keeps us from clearly stating how we used the limit of a product, other than again referring to a pattern: "Use the limit of a product n-1 times." The use of induction makes this precise.

Proof:
We prove by induction.
1) First, we show that f(x) = x¹ = x is continuous. (This is the starting point)
But this is already known: lim_{x → c} x = c.
So f is continuous at any point c.
The statement is true when n=1.
2) Second, we assume that f(x) = xⁿ is continuous and now show that this implies that g(x) = xⁿ⁺¹ is also continuous. (This is the inductive step)
So assume that f is continuous.
g(x) = x f(x) (Relate the new function in terms of what is assumed)
So using the limit of a product:
lim_{x → c} g(x) = lim_{x → c} x f(x) = c f(c) = c cⁿ = cⁿ⁺¹ = g(c)
So xⁿ⁺¹ is continuous whenever xⁿ is continuous.

So by induction, since the statement is true for n=1, and whenever the statement is true for one value n it is also true for the next value n+1, the statement is true for all integers starting with 1.
(End of Proof)

Sometimes induction is compared to reaching different rungs on a ladder. The first statement is what allows you to climb onto the first step. The inductive implication is what says that if you have already reached one rung, then you can move to the next rung. Putting the two together, you first climb on the ladder's first rung. Then you know that you can climb from the first to the second rung, from the second rung to the third rung, from the third to the fourth, and so on forever. The implication, in one fell swoop, justifies climbing each step from the previous. The principle of mathematical induction replaces the uncertainty in "..."