gen-define-mathematical-induction-and-give-one-short-worked-exam-60e7

Define mathematical induction and give one short worked example.

# Mathematical Induction **Mathematical induction** is a proof technique used to prove that a statement P(n) is true for all natural numbers n ≥ n₀ (usually n₀ = 1). ## The Method 1. **Base case**: Prove P(n₀) is true 2. **Inductive step**: Assume P(k) is true for some arbitrary k ≥ n₀ (this is the *inductive hypothesis*), then prove P(k+1) is true If both steps succeed, P(n) is true for all n ≥ n₀. ## Example **Prove:** 1 + 2 + 3 + ... + n = n(n+1)/2 for all n ≥ 1 **Base case (n=1):** - Left side: 1 - Right side: 1(1+1)/2 = 1 ✓ **Inductive step:** Assume true for n = k: $$1 + 2 + ... + k = \frac{k(k+1)}{2}$$ Prove for n = k+1: $$1 + 2 + ... + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$$ $$= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$$ This matches the formula with n = k+1. ✓ **Conclusion:** The formula holds for all n ≥ 1. ∎