Mathematical Induction (idea)

Mathematical induction is a useful technique for proving very general mathematical statements to be true. In terms of discrete mathematics, it is used to prove propositions that describe the entire set of positive integers.

A proof by mathematical induction that a given proposition P(n) is true for every positive integer n consists of two steps.

1. The basis step is the demonstration that P(1) is true. This is usually the easier of the two parts.
2. The inductive step is the demonstration that P(n) always implies that P(n+1), and that this implication is true for any n. This is usually the harder of the two parts.

Thus, we first make sure that P(1) is true, then we work forward from there using the inductive step, stating that if P(n) is true, so must P(n+1). It is very important to realize that induction is not assuming that P(n) is true for all positive integers; it is only saying that if P(n) is true, then P(n+1) is also true; a narrow distinction, but an important one.

One can think of mathematical induction as being much like dominos stacked on end. Let P(n) be the proposition that domino n is knocked over. If the first domino is knocked over - or, in other words, P(1) is true, or the basis step - and if, whenver the nth domino is knocked over, it also knocks over the (n+1)th domino - in other words, P(n) -> P(n+1) is true - then all the dominos are knocked over.

Let's look at an example of mathematical induction.

Prove that the sum of the first n odd positive integers (i.e., 1, 3, 5, ... ) is n^2.

Basis step P(1) = sum of the first one positive odd integer = 1^2 = 1, so this is true.

Inductive step We need to show that P(n) implies P(n+1) for all n. Let's reduce P(n) to an equation:
1 + 3 + 5 + ... + (2n-3) + (2n-1) = n^2
... as well as P(n+1) to an equation:
1 + 3 + 5 + ... + (2n-1) + (2n+1) = (n+1)^2

If we assume that P(n) is true, let's subsitute it into the equation for P(n+1). We start off by duplicating what's on the left side of the P(n+1) equation, because the left side is equal to itself:

1 + 3 + 5 + ... + (2n-1) + (2n+1) = { 1 + 3 + 5 + ... + (2n-1) } + (2n+1) 
                                  = n^2 + (2n+1)
                                  = n^2 + 2n + 1  ... and now we factor it ...
                                  = (n + 1)^2

In other words, the statement for P(n+1) is true if P(n) is true, thus completing the inductive step.

Mathematical induction is used regularly to solve such problems as distribution of various values of stamps and determining how floor tiles should be laid. It's also an invaluable tool of the computer scientist in making algorithms run faster.