- Because this is a formal subject, the textbook is full of proofs
- Proofs are encapsulated understanding
- You may be asked to learn a very few important proofs

- Prove something about P1 (the
*basis*) - Prove that if it is true for Pn, then it is true for Pn+1 (the
*inductive assumption*) - Conclude that it is true for all P

- Assume some fact P is false
- Show that this leads to a contradiction
- Conclude P must be true

Copyright © 1996 by David Matuszek

Last modified Jan 29, 1996