5.4 PROOF BY MATHEMATICAL INDUCTION 181Students sometimes complain that the actual induction proof seems like
an afterthought, after a "seemingly sufficient" number of special cases of a
statement have been verified as true. Keep in mind that no (necessarily
finite) number of verifications of specific cases is ever enough to prove that
a statement is true for every positive integer. Exercise 11 is a case in point.
A second complaint often heard is that, in the course of an induction proof,
assumption is made of what we are trying to prove when the induction hy-
pothesis is stated. For instance, in Example 1, we wanted to prove p(n):
1 + 3 + -.. + (2n - 1) = n2; did we not assume precisely that equation at
the start of part (2) of the proof? The distinction lies in the use of quanti-
fiers. Our desired result in Example 1 is (Vn)(p(n)). Our assumption is
simply dm), where m is some fixed positive integer, our goal being to deduce
p(m + 1) for that m. A third problem is that because part (i) of most induc-
tion proofs is often trivial to prove, students are sometimes tempted to omit
it or gloss over it. Exercise 10 demonstrates the dangers of such an attitude.
CATEGORIES OF INDUCTION PROOFThere are certain mathematical situations that lend themselves especially
well to proof by induction. In the following paragraphs we consider three
such situations. These three categories are by no means exhaustive.
Summation formulas. The result in Example 2 is a simple representative of
a large class of theorems whose proofs use the induction technique. Such
a theorem is known as a summation formula, a formula that yields, for each
positive integer n, the sum of n numbers of a prescribed form. Part (b) of
Example 1 is also in this category. Formulas of this type are often said to
be a closed form representation of the given sum.
Summation formulas are usually expressed by means of summation no-
tation, whereby we abbreviate a sum x, + x, +.. - + x, by the symbol
==, x,. Using this notation, we may rewrite Example 2 in the form
z=, (2k - 1) = n2 and Example l(b) as '&, k = [n(n + 1)]/2. The vari-
able k in such a formula is a dummy variable (recall the discussion following
Example 1, Article 3.2); the letters i, j, and k are the letters most commonly
used for this purpose. As further examples, the symbol x=, (2j) rep-
resents the sum 6 + 8 + 10 + ... + 2n, while Cf=, (-1)' i stands for
-l+2-3+4-5.
Here are two more examples of induction proofs of summation formulas.
It should be noted that the induction method is of no assistance in dis-
covering the formula, but only for proving that a given formula actually
represents a particular sum.
EXAMPLE 4 Prove that, for each positive integer n, the sum E= (k/2*) is
given by the formula 2 - [(n + 2)/2"]. (You should first "try out" the
formula for several special cases.)