Overview

Induction and extremal arguments prove statements by reducing to smaller or more extreme cases.

Key Ideas

• Strong induction assumes all smaller cases, not just $n-1$.
• Minimal counterexample arguments often lead to contradictions.
• Extremal elements (smallest or largest) are powerful anchors.

Worked Example

Prove that any amount of postage $n\ge12$ can be formed using 4-cent and 5-cent stamps. Use induction with base cases $12,13,14,15$, then add $4$.

Practice Problems