Proof techniques

• 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