• Principle of Mathematical Induction, a logical approach.
• Principle of Mathematical Induction, a mathematical approach.
• Sum of the first n integers, an example.

Suppose

P(1) is true; and

for all integers k ³ 1, if P(k) is true then P(k + 1) is true.

The truth of statement (2) implies, according to the law of universal instantiation, that no matter what particular integer k ³ 1 is substituted in place of k, the statement "If P(k) then P(k + 1)" is true. The following argument, therefore, has true premises, and so by modus ponens it has a true conclusion:

Similar reasoning gives the following chain of arguments, each of which has a true conclusion by modus ponens:

Thus no matter how large a positive integer n is specified, the truth of P(n) can be deduced as the final conclusion of a (possibly very long) chain of arguments continuing those shown above.

Principal of Mathematical Induction: top

Let P(n) be a predicate, whose domain is Z. Let m be a fixed given integer. If the following statements are true:

1. P(m) is true.
2. For any specific integer k ³ m, if P(k) is true, then P(k + 1) is true.

Example: Sum of the first n integers. Prove that . top

Proof: (by induction)

Let P(n): . [We must show that P(1) is true in the basis step and that P(k + 1) is true in the induction step.]

Basis Step: P(1) is true: The sum of i from i =1 to 1 is just 1 and 1(1 + 1)/2 = 1.

Inductive Step: For k ³ 1, suppose P(k) is true, that is . We must prove that

.

Now, given , we have

\ P(k + 1) follows from P(k) for k ³ 1. So by the PMI, P(n) is true for all n ³ 1. QED

PMI: P(n) defined for all n ³ m, where m is a given, fixed integer. If the following two statements are true:

1. P(m) is true. (Basis statement)
2. " k ³ m, P(k) ® P(k + 1). (Inductive statement)

Then P(n) is true for all n Î z, n ³ m.

top An outline for the Principal of Mathematical Induction.