This paper is a redo of an article that first appeared in the Arizona Journal of Natural Philosophy, July, 1991. Russell and Poincare, taking widely differing views on mathematical induction, argued about what it meant and how it was to be justiffed. Poincare thought of it as mysterious; Russell claimed to have removed its mystery. Decades later, today's student must wrestle with it to solve textbook problems, but how often do they understand what they're doing? Honk if you hate mathematical induction PDF file
This paper is a redo of an article that first appeared in the Arizona Journal of Natural Philosophy, April, 1993, which was itself a reprint from the January 1987 issue. If you've ever wished for a better way to use mathematical induction in proofs, here it is, though this techinque works best on problems that reduce finite sums or products to closed form (a compact expression).
Mathematical Induction for Students PDF file In this paper, we learn how to formulate proofs of certain sums and/or products to have closed forms, such as establishing that
1 + 2 + ⋅⋅⋅ + n = (1/2)n(n+1), (1)
for n ≥ 1. We can represent this generally as
L(n) = R(n), (2a)
where the L stands for left-hand side, and the R stands for the right-hand side. Let a be the smallest integer that satisfies (2), then we must show that
L(a) = R(a). (2b)
Then, by assuming
L(k) = R(k), (3)
we must show that
L(k+1) = R(k+1). (4)
So, to use this method to prove (1), we show the base case, a = 1, or, that L(1) = R(1).
Next, assuming that (3) is true, or that
1 + 2 + ⋅⋅⋅ + k = (1/2)k(k+1), (5)
we must then show that (4) is true. This is usually done by adding the (k+1)st term to both sides,
1 + 2 + ⋅⋅⋅ + k + (k+1) = (1/2)k(k+1) + (k+1), (6)
and then simplifying, which establishes (4).
To summarize, the standard method of proof follows this reasoning: ascerting (3), we must then show (4), or that
L(k) = R(k) ⇒ L(k+1) = R(k+1). (7)
Our alternative method of proof follows this reasoning: the method is to use the following as equivalent to (7):
L(k) = R(k) ⇒ L(k+1) - L(k) = R(k+1) - R(k) ⇒ L(k+1) = R(k+1). (8)
The advantage of this method is that using differences is often the easier way to make a proof.
The reasoning this method works is because if we can show that the differences are equal, then, because we have ascerted the truth of (3), we just add L(k) = R(k) to both sides the equation in (8) to get (4). In other words, it is not possible that the differences are equal but that (4) is not true.
This difference method was used by George Polya in his book Induction and Analogy in Mathematics, 5th ed. pp. 108--110, Princeton University Press (1965).
Now we try this on a real problem. By using this alternative form of mathematical induction, let's prove Nicomachus's Theorem that
13 + 23 + ⋅⋅⋅ + n3 = (1 + 2 + ⋅⋅⋅ + n)2, (9)
for n ≥ 1.
The equation is obviously true for n = 1. Next, we assume (3) is true and then take differences, as prescribed in (8). Now, we must show that
(k+1)3 = (1 + 2 + ⋅⋅⋅ + k+1)2 - (1 + 2 + ⋅⋅⋅ + k)2. (10)
But, the RHS is the difference of two squares, yielding
(1 + 2 + ⋅⋅⋅ + k+1)2 - (1 + 2 + ⋅⋅⋅ + k)2 = [(1 + 2 + ⋅⋅⋅ + k+1) + (1 + 2 + ⋅⋅⋅ + k)] [(1 + 2 + ⋅⋅⋅ + k+1) - (1 + 2 + ⋅⋅⋅ + k)]
= [2(1 + 2 + ⋅⋅⋅ + k) + (k+1)][k+1]
= [k(k+1) + (k+1)][k+1] (using eq. (1))
= [k+1]3. (11)
Thus, we have established Nicomachus's Theorem!