Java Reference
In-Depth Information
Proving either variant of the induction step (in conjunction with verifying the base
case) yields a satisfactory proof by mathematical induction.
The two conditions that make up the induction proof combine to demonstrate
that Thrm holds for n = 2 as an extension of the fact that Thrm holds for n = 1.
This fact, combined again with condition (2) or (2a), indicates that Thrm also holds
for n = 3, and so on. Thus, Thrm holds for all values of n (larger than the base
cases) once the two conditions have been proved.
What makes mathematical induction so powerful (and so mystifying to most
people at first) is that we can take advantage of the assumption that Thrm holds
for all values less than n as a tool to help us prove that Thrm holds for n. This is
known as the induction hypothesis. Having this assumption to work with makes
the induction step easier to prove than tackling the original theorem itself. Being
able to rely on the induction hypothesis provides extra information that we can
bring to bear on the problem.
Recursion and induction have many similarities. Both are anchored on one or
more base cases. A recursive function relies on the ability to call itself to get the
answer for smaller instances of the problem. Likewise, induction proofs rely on the
truth of the induction hypothesis to prove the theorem. The induction hypothesis
does not come out of thin air. It is true if and only if the theorem itself is true, and
therefore is reliable within the proof context. Using the induction hypothesis it do
work is exactly the same as using a recursive call to do work.
Example2.11
Here is a sample proof by mathematical induction. Call
the sum of the first n positive integers S(n).
Theorem2.2
S(n) = n(n + 1)=2.
Proof:
The proof is by mathematical induction.
1. Check the base case. For n = 1, verify that S(1) = 1(1 + 1)=2. S(1)
is simply the sum of the first positive number, which is 1. Because
1(1 + 1)=2 = 1, the formula is correct for the base case.
2. State the induction hypothesis. The induction hypothesis is
n
X
(n 1)((n 1) + 1)
2
(n 1)(n)
2
S(n 1) =
i =
=
:
i=1
3. Use the assumption from the induction hypothesis forn
1 to
show that the result is true forn. The induction hypothesis states
that S(n 1) = (n 1)(n)=2, and because S(n) = S(n 1) + n,
we can substitute for S(n 1) to get
n
X
!
X
n
(n 1)(n)
2
i =
i
+ n =
+ n
i=1
i=1
