Mathematical Induction
Mathematical induction is a powerful tool in proof-writing. Let's
say Nate has a statement Sn that he wants to prove for n = 1,
2, 3, ... in other words for all n in N, the set of natural
numbers. How can he do this? First, prove that Sn is true for
n=1 (that S1 is true). Then, prove that if Sk is
true for some natural number k, then Sk+1 must also be
true. If you really want a proof that this works, click here.
Example: Prove that 1+2+3+...+(2n-1) = n2 for all natural
numbers n.
Solution: This is true for n=1 because we have 1=1. Now assume it is
true for n=k:
(k+1)2 = 1 + 2 + 3 + ... + (2k-1) + [2(k+1)-1]
(k+1)2 = k2 + (2k+1) (since we assume it
is true for n=k)
(k+1)2 = k2+2k+1 = (k+1)2
which is true for any value of k. Therefore Sn is true
for all natural numbers.
Click here to
close this window.
The Proof of Induction
Assume that we have proven that a statement Sn is true for n=1
and that Sk implies Sk+1. Now assume for the sake of
contradiction that there is a nonempty set A of all values
ai for which S is false. By the Well-Ordering Principle
(all non-empty sets of natural numbers have a least element), A has a
smallest value a0. Since Sa0 is false, then
one of two things must be true: Either (a0-1) is not a
natural number or Sa0-1 is false. The first case is only
possible if a0 is 1, but we have already shown that
S1 is true, so that is not possible. The second case is also
impossible because then (a0-1) would be in A, which
contradicts the assumption that a0 is the smallest
element in A. Since neither case is possible, induction must be
valid. QED.