Mathematical Induction

Math for CS · Axiom Academy

Prove properties of all natural numbers using a base case and recursive step Mathematical induction proves that a property P(n) is true for all natural numbers n. It relies on two components: Base Case: Show that P(1) is true (or P(0), depending on context) Inductive Step: Show that if P(k) is true for some k, then P(k+1) must be true If both parts are proven, then P(n) is true for all natural numbers n ≥ 1. Claim: For all positive integers n: Inductive Step: Assume the formula is true for n = k: We must show it's true for n = k+1: Conclusion: By mathematical induction, the formula holds for all positive integers n. Claim: For all non-negative integers n: Conclusion: The formula holds for all non-negative integers n. Assume P(j) is true for all j ≤ k Use strong induction when proving P(k+1) requires knowing P(j) for multiple previous values, not just P(k).

This is the written version of the interactive lesson above. See the full Math for CS course.