Course contentsShow
← Mathematics
Lesson 2501 of 3,12150. Discrete Math — Logic and ProofFree lesson

The Principle of Mathematical Induction

Understanding induction as a proof technique for statements indexed by natural numbers and its foundational role.

The Principle of Mathematical Induction

What you'll learn: How to prove statements about all natural numbers using a two-step domino effect.

The Core Idea

Mathematical induction is a powerful proof technique for statements indexed by natural numbers (like n = 1, 2, 3, ...). Instead of checking infinitely many cases one-by-one, induction works like toppling dominoes: prove the first domino falls, then prove that whenever one domino falls, the next one must fall too. This guarantees all dominoes fall.

The Two-Step Structure

Step 1: Base Case
Verify the statement is true for the starting value (usually n = 1 or n = 0). This is like pushing the first domino.

Step 2: Inductive Step
Assume the statement is true for some arbitrary natural number k (this assumption is called the inductive hypothesis). Then prove the statement must also be true for k + 1. This is like showing that if domino k falls, it knocks over domino k + 1.

Why It Works

Induction relies on the well-ordering principle of natural numbers: every natural number can be reached by starting at 1 and adding 1 repeatedly. If the base case holds and each step leads to the next, you've created an unbreakable chain proving the statement for all natural numbers.

Example Pattern

To prove "For all n ≥ 1, the sum 1 + 2 + ... + n = n(n+1)/2":

  1. Base case: When n = 1, left side = 1, right side = 1(2)/2 = 1. ✓
  2. Inductive step: Assume true for k. Show it's true for k + 1 using that assumption.

Key Takeaway: Mathematical induction proves infinitely many statements in two finite steps: establish the base case and prove the inductive chain reaction.