Types of proof

• proof by construction
  • e.g. For any two sets A and B, A' ⋂ B' = (A ⋃ B)’
• proof by contradiction
  • e.g. \sqrt 2 is irrational
• proof by induction
  • Basis: Prove that P(1) is true.
  • Induction step: For each i≥1, assume that P(i) is true and use this assumption to show that P(i + 1) is true.

Finite automata