CSci 271 Lecture Notes
Week Six, Monday: Methods of Proof and Induction
Introduction
A theorem is a statement that can be proved true. The
rules of inference tie together the steps of a proof.
Rules of Inference
The rules of inference are tautologies, e.g., modus ponens
states that if both an implication and its hypothesis are true then
the conclusion of the implication is true.
An argument built using rules of inference is said to be valid.
Fallacies
- Affirming the conclusion
- Denying the hypothesis
- Circular reasoning
Methods of Proving Theorems
- Vacuous proof
- Trivial proof
- Direct proof
- Indirect proof
- Proof by contradiction
- Proof by cases
Theorems and Quantifiers
Existence proof (constructive and nonconstructive).
Some Comments on Proofs
An algorithm for proving theorems does not exist. Constructing
proof is an art that can be learned by doing. Goldbach's conjecture
(every even positive integer greater than two is the sum of two primes) has yet
to be proven.
The Well-Ordering Property
Every nonempty set of nonnegative integers has a least element.
Mathematical Induction
A proof by mathematical induction that P(n) is true for all positive integers n consists
of two steps:
- Basis step. P(1) is shown to be true.
- Inductive step. P(n) implies P(n + 1) is shown to be true for every positive integer n.
Examples of Proofs by Mathematical Induction
Example 2
Example 6
Example 8
Second principle of Mathematical Induction
Example 13
Example 14
This page established October 9, 1998; last updated October 9, 1998.