Page 334 - Discrete Mathematics and Its Applications

5.1 Mathematical Induction 313

induction has two parts, a basis step, where we show that P(1) is true, and an inductive step,
where we show that for all positive integers k,if P(k) is true, then P(k + 1) is true.

PRINCIPLE OF MATHEMATICAL INDUCTION To prove that P (n) is true for all
positive integers n, where P (n) is a propositional function, we complete two steps:

BASIS STEP: We verify that P(1) is true.
INDUCTIVE STEP: We show that the conditional statement P(k) → P(k + 1) is true for
all positive integers k.

To complete the inductive step of a proof using the principle of mathematical induction, we
assume that P(k) is true for an arbitrary positive integer k and show that under this assumption,
P(k + 1) must also be true. The assumption that P(k) is true is called the inductive hypothesis.
Once we complete both steps in a proof by mathematical induction, we have shown that P (n) is
true for all positive integers, that is, we have shown that ∀nP (n) is true where the quantification
is over the set of positive integers. In the inductive step, we show that ∀k(P (k) → P(k + 1))
is true, where again, the domain is the set of positive integers.
Expressed as a rule of inference, this proof technique can be stated as

(P (1) ∧∀ k(P (k) → P(k + 1))) →∀ nP (n),

when the domain is the set of positive integers. Because mathematical induction is such an
important technique, it is worthwhile to explain in detail the steps of a proof using this technique.
The first thing we do to prove that P (n) is true for all positive integers n is to show that P(1) is
true. This amounts to showing that the particular statement obtained when n is replaced by 1 in
P (n) is true. Then we must show that P(k) → P(k + 1) is true for every positive integer k.To
prove that this conditional statement is true for every positive integer k, we need to show that
P(k + 1) cannot be false when P(k) is true. This can be accomplished by assuming that P(k)
is true and showing that under this hypothesis P(k + 1) must also be true.

Remark: In a proof by mathematical induction it is not assumed that P(k) is true for all positive
integers! It is only shown that if it is assumed that P(k) is true, then P(k + 1) is also true. Thus,
a proof by mathematical induction is not a case of begging the question, or circular reasoning.

When we use mathematical induction to prove a theorem, we first show that P(1) is true. Then
we know that P(2) is true, because P(1) implies P(2). Further, we know that P(3) is true,
because P(2) implies P(3). Continuing along these lines, we see that P (n) is true for every
positive integer n.

HISTORICAL NOTE The first known use of mathematical induction is in the work of the sixteenth-century
mathematician Francesco Maurolico (1494 –1575). Maurolico wrote extensively on the works of classical
mathematics and made many contributions to geometry and optics. In his book Arithmeticorum Libri Duo,
Maurolico presented a variety of properties of the integers together with proofs of these properties. To prove
some of these properties, he devised the method of mathematical induction. His first use of mathematical
2
induction in this book was to prove that the sum of the first n odd positive integers equals n . Augustus De
Morgan is credited with the first presentation in 1838 of formal proofs using mathematical induction, as well
as introducing the terminology “mathematical induction.” Maurolico’s proofs were informal and he never used
the word “induction.” See [Gu11] to learn more about the history of the method of mathematical induction.