Mathematical Induction
A rigorous proof technique for verifying formulas for all natural numbers n.
Introduction
How do you prove something is true for every natural number? Mathematical induction is like climbing an infinite ladder: prove you can get on the first rung, then prove that from any rung you can always reach the next. This two-step process proves the statement for all n.
Prerequisite Connection
You understand sequences, series, and sigma notation.
Today's Increment
We master the base case and inductive step to prove formulas rigorously.
Why This Matters
Induction is fundamental in computer science, number theory, and proving the correctness of algorithms.
Key Concepts
Step 1: Base Case
Prove the statement is true for (or the starting value).
Step 2: Inductive Hypothesis
Assume the statement is true for some arbitrary .
Step 3: Inductive Step
Prove that if true for , then it must be true for .
The Domino Effect
Base case knocks down the first domino. Inductive step ensures each domino knocks down the next. All dominoes fall!
Worked Examples
Example 1: Sum Formula (Basic)
Prove:
Base Case (n = 1):
Left: 1. Right: ✓
Inductive Step: Assume true for k, prove for k+1:
This matches the formula for n = k+1. ✓ Proved!
Example 2: Divisibility (Intermediate)
Prove: is divisible by 2 for all
Base Case (n = 1):
, which is divisible by 2 ✓
Inductive Step:
Both terms divisible by 2 (by hypothesis and directly) ✓
Proved by induction!
Example 3: Inequality (Advanced)
Prove: for all
Base Case (n = 1):
✓
Inductive Step:
Need: , i.e.,
For : , so ✓
Proved by induction!
Common Pitfalls
Skipping the base case
Without the base case, the inductive step proves nothing!
Not using the hypothesis
The inductive step must USE the assumption that P(k) is true.
Circular reasoning
You can't assume P(k+1) is true—you must derive it from P(k).
Real-World Application
Algorithm Correctness
Computer scientists use induction to prove algorithms work correctly. For recursive algorithms, the base case is the simplest input, and the inductive step shows that if the algorithm works for smaller inputs, it works for the next size up.
Example: Proving merge sort correctly sorts any list of n elements.
Practice Quiz
Loading...