Revise: Mathematical Induction
The principle of mathematical induction, and using it to prove summation, divisibility, and inequality statements.
Base case + inductive step (P(k) true ⟹ P(k+1) true) ⟹ P(n) true for all n.
Domino analogy: first domino falls, each knocks the next.
Add the (k+1)th term to both sides, then simplify with algebra.
1+2+...+10 = 55.
Assume f(k)=d·m, rewrite f(k+1) in terms of f(k), then factor out d.
3ⁿ−1 divisible by 2 for all n≥1.
Base case can start anywhere; multiply by positives to preserve inequalities.
n! > 2ⁿ for all n≥4.
Both steps are required — skipping either invalidates the proof.
n < 2ⁿ for all n≥1.
The inductive step must explicitly connect back to the inductive hypothesis.
k(k+1)/2 + (k+1) = (k+1)(k+2)/2.
Rewriting f(k+1) in terms of f(k) is the essential algebraic move.
5¹−1=4, divisible by 4.
Compare growth rates (e.g. factorial vs exponential) using induction.
7! = 5040 > 3⁷ = 2187.