An introductory course designed to teach the fundamental concepts and techniques of mathematical proofs.
Mathematical induction is a proof technique used to show that a statement holds for all natural numbers.
If both steps work, the statement is true for all natural numbers!
Induction is like climbing a ladder: if you can get on the first step, and you can always go to the next step, you can climb forever.
\[ \text{If statement is true for } n = 1, \text{ and } \forall k, \text{ true for } n = k \Rightarrow \text{ true for } n = k+1, \text{ then true for all } n. \]
\[P(1) \wedge (P(k) \Rightarrow P(k+1)) \Rightarrow \forall n \in \mathbb{N}, P(n)\]
Proving that the sum of the first \( n \) natural numbers is \( \frac{n(n+1)}{2} \).
Showing that \( 2^n > n \) for all \( n \geq 1 \).
Induction proves statements are true for all natural numbers by climbing from one case to the next.