Q: Prove by strong induction: every integer n ≥ 2 is prime or a product of primes. Base: 2 is prime. Strong hypothesis: assume true for all 2 ≤ m < k. For k: if k prime, done. Else k = ab with 2 ≤ a,b < k. By hypothesis a, b are prime/products - so k is a product of primes! (Weak induction fails: k-1 being factored says nothing about k's factors!)