Lecture on Proofs and Induction

Overview

• Introduction by MIT OpenCourseWare: Support for free educational resources. Visit MIT OpenCourseWare for more details.

Key Components of Proofs

• Propositions, Axioms, and Logical Deductions
  • Reasonable assumptions are acceptable.
  • No need to know specific terms like modus ponens.
  • Axioms should be consistent.
• Example: Proving a proposition on an exam must be based on elementary facts, not just stating it as axioms.
• Direct Proofs
  • Start with axioms and known theorems, make logical deductions to reach the theorem.

Indirect Proofs

• Proof by Contradiction
  • Assume the opposite of what you're trying to prove (not p).
  • Make logical deductions to reach a contradiction (falsehood).
  • Conclude the original proposition (p) is true.

Example: Proof that √2 is Irrational

1. Proof by contradiction: Start by assuming √2 is rational.
2. Step-by-step deduction:
   • Express √2 as a fraction a/b in lowest terms.
   • Derive 2b² = a², implying a and b must be even.
   • Contradiction: a/b was assumed to be in the lowest terms.
3. Conclusion: √2 is irrational.

Historical Context

• Pythagoreans in Ancient Greece
  • Belief in no irrational numbers, only rational numbers were finite and good.
  • Discovery of √2 being irrational led to a crisis and cover-up.
  • Legend of Deep Throat who leaked this proof.

False Proofs

• Example: Proving 90 > 92
  • Demonstrated misleading use of diagrams and assumptions.
  • Importance of ensuring diagrams are to scale and accurate in proofs.

Induction

• Definition and Basic Form of Induction
  • Let P(n) be a predicate.
  • Prove the base case (P(0) is true).
  • Show that for all natural numbers n, if P(n) then P(n+1) is true.
  • Conclude P(n) is true for all n.

Example Proofs Using Induction

• Sum of Natural Numbers
  • Prove 1 + 2 + ... + n = n(n+1)/2 using induction.
  • Base case: P(0) holds.
  • Inductive step: Assume P(n) is true, show P(n+1) follows.
• 3 Divides n³ - n
  • Use induction to prove for all n.
  • Base case: n=0 holds.
  • Inductive step: Use given and rearrange to show result holds.

Problems and Edge Cases

• Inductions Starting at Different Values
  • Inductions can start at any integer b, not just 0 or 1.
• False Proof Example: All horses are the same color
  • Base case: Set of one horse.
  • Inductive step: Show for n+1 horses if true for n.
  • Flaw: Induction doesn't hold for transitions like P1 → P2.

Advanced Induction: Stronger Hypotheses

• Example: Tiling a 2^n x 2^n courtyard with one missing square.
  • Divide and use the L-shaped tiles method.
  • Proof by induction becomes easier with stronger hypotheses.
• Strategies
  • When stuck, try proving a stronger hypothesis.
  • Use the stronger hypothesis to simplify proofs and solve complex problems.

Conclusion

• Induction is a powerful tool for proving propositions.
• Understanding and practicing the method ensures mastery of proofs in computer science.