Lesson 060
Mathematical Proofs & Induction
Direct · Contradiction · Induction
1:00The four core proof techniques — direct, contrapositive, contradiction, cases — and mathematical induction, from the domino analogy through loop invariants and the handshake lemma.
By the end, you can
- Explain why testing can disprove but never prove a universal claim.
- Distinguish the contrapositive (equivalent) from the converse (not equivalent) of an implication.
- Apply all four proof techniques to appropriate problem shapes.
- Write a complete induction proof: state P(n), prove the base case, state and use the inductive hypothesis, prove the inductive step, conclude.
- Identify the inductive hypothesis and explain what you are allowed to assume during the inductive step.
- Explain why omitting the base case invalidates an induction argument.
- Distinguish weak induction from strong induction and choose the appropriate form.
- Map initialization, maintenance, and termination of a loop-invariant argument onto the parts of an induction proof.
- Apply the handshake lemma and derive the even-odd-degree corollary.
Up next in Recursion, Paradigms & Algorithm Analysis
