Java Reference
In-Depth Information
Theorem2.1
There is no largest integer.
Proof:
Proof by contradiction.
Step 1. Contrary assumption: Assume that there is a largest integer.
Call it B (for “biggest”).
Step 2. Show this assumption leads to a contradiction: Consider
C = B + 1. C is an integer because it is the sum of two integers. Also,
C > B, which means that B is not the largest integer after all. Thus, we
have reached a contradiction. The only flaw in our reasoning is the initial
assumption that the theorem is false. Thus, we conclude that the theorem is
correct.
2
A related proof technique is proving the contrapositive.
We can prove that
P ) Q by proving (not Q) ) (not P).
2.6.3
Proof by Mathematical Induction
Mathematical induction can be used to prove a wide variety of theorems. Induction
also provides a useful way to think about algorithm design, because it encourages
you to think about solving a problem by building up from simple subproblems.
Induction can help to prove that a recursive function produces the correct result..
Understanding recursion is a big step toward understanding induction, and vice
versa, since they work by essentially the same process.
Within the context of algorithm analysis, one of the most important uses for
mathematical induction is as a method to test a hypothesis. As explained in Sec-
tion 2.4, when seeking a closed-form solution for a summation or recurrence we
might first guess or otherwise acquire evidence that a particular formula is the cor-
rect solution. If the formula is indeed correct, it is often an easy matter to prove
that fact with an induction proof.
Let Thrm be a theorem to prove, and express Thrm in terms of a positive
integer parameter n. Mathematical induction states that Thrm is true for any value
of parameter n (for n c, where c is some constant) if the following two conditions
are true:
1. Base Case: Thrm holds for n = c, and
2. Induction Step: If Thrm holds for n 1, then Thrm holds for n.
Proving the base case is usually easy, typically requiring that some small value
such as 1 be substituted for n in the theorem and applying simple algebra or logic
as necessary to verify the theorem. Proving the induction step is sometimes easy,
and sometimes difficult. An alternative formulation of the induction step is known
as strong induction. The induction step for strong induction is:
2a. Induction Step: If Thrm holds for all k, c k < n, then Thrm holds for n.
