Course contentsShow
← Computer Science
Lesson 86 of 2,8722. Discrete Mathematics for CSFree lesson

The Principle of Mathematical Induction

Understanding the foundation: proving a statement for all natural numbers using base case and inductive step.

The Principle of Mathematical Induction

What you'll learn: How to prove that a statement holds true for all natural numbers by establishing a starting point and showing each step leads to the next.

The Core Idea

Mathematical induction is like climbing an infinite ladder. If you can:

  1. Step onto the first rung (prove it's true for a starting case, usually n=0 or n=1)
  2. Prove that whenever you're on any rung k, you can reach the next rung k+1 (prove that if it's true for n=k, then it must be true for n=k+1)

...then you can climb the entire ladder—the statement is true for all natural numbers.

The Two Essential Parts

Base Case

Verify your statement is true for the smallest value (often n=0 or n=1). This is your foundation.

Inductive Step

Assume the statement is true for some arbitrary natural number k (this assumption is called the inductive hypothesis). Then prove it must also be true for k+1.

Why This Works

Think of dominoes: if you knock over the first domino (base case) and you've arranged them so that any falling domino knocks over the next one (inductive step), then all dominoes will fall.

In CS, induction proves correctness of recursive algorithms, validates formulas involving sequences and summations, and establishes properties of data structures.

Example structure:

  • Claim: Some property P(n) holds for all n ≥ 1
  • Base: Show P(1) is true
  • Inductive: Assume P(k) is true; prove P(k+1) follows

Key Takeaway: Mathematical induction proves statements for all natural numbers using two steps: establish a base case, then show that truth at any step k guarantees truth at step k+1.