Table of Contents   |   Glossary

---

Proof Methods

Direct Proofs

• Introduction
• Making Your Proofs Rigorous
• Common Errors in Proofs
• Sample Problems

Proofs by Contradiction

• A Proof by Contradiction
• Where to Use Proofs by Contradiction
• Problems

Inductive Proofs

• Understanding Mathematical Induction
• Formulating a Proof by Induction
• Induction and Recursion
• Pitfalls
• Other Induction Topics
  • Forming a Stronger Hypothesis
  • Proofs of Algorithmic Correctness
  • Proofs of Running Time
  • Strong Induction
• Problems

The Adversarial Method

• Who is the Adversary?
• The Basic Adversarial Method
• Sample Problems

Some Mathematical Aids

• Function Notation
• Exponential Identities
• Logarithmic Identities
• Summation Identities
• Transformation Tricks