82 CHAPTER 2 Discrete Mathematics
does give us a convenient language in which to streamline certain argu-
ments. Namely, when we consider an integernfor whichP(m) is true
for allm < n, we typically simply say,
By induction,P(m) is true for allm < n.Let’s see how to use this language in the above two examples.Example 1. Any integern≥ 2 has at least one prime factor.
Proof. We shall prove this by induction onn≥2. Since 2 is a prime
factor of itself, we see that the induction starts. Next, assume thatnis
a given integer. Ifn is prime then, of course, there’s nothing to prove.
Otherwise, n factors as n = ab, where a and b are positive integers
satisfying 2≤a, b < n. By inductionahas a prime factor, and hence
so does n. Therefore, by the principle of mathematical induction we
conclude that every integern≥2 has a prime factor and the proof is
complete.
Example 2. For any integern≥ 1 one has
12 + 2^2 + 3^2 +···+n^2 =
n(n+ 1)(2n+ 1)
6.
Proof. We prove this by mathematical induction. The above is clearly
true for n = 1, and so the induction starts. Next, let n be a given
integer. By induction we assume that the above recipe is valid for all
positive integersm < n. We compute:
12 + 2^2 + 3^2 +···+n^2 = 1^2 + 2^2 + 3^2 +···+ (n−1)^2 +n^2=n(n−1)(2n−1)
6
+n^2 (by induction)=n(n+ 1)(2n+ 1)
6
and the proof is complete.
Exercises