Induction
To prove a claim for every whole number n, show it for n = 1 (base case). Then show that truth for n = k forces truth for n = k + 1.
Last updated
Analogy
Dominoes: knock over the first, and make sure each one knocks the next. All of them fall.
Example
Base n = 1: 1 = 1(2)/2. True.Assume it holds for n = k.Add k+1: k(k+1)/2 + (k+1) = (k+1)(k+2)/2.That is the formula for n = k+1.
In practice
Use it for sums, divisibility and formulas that depend on a whole number n.
Practice
Flashcards
- What are the two parts of a proof by induction?The base case, then the inductive step from n = k to n = k + 1.
Interview questions
- Prove by induction that 1 + 2 + ... + n = n(n+1)/2 for every whole number n >= 1.
- Base case n = 1: both sides equal 1
- Assume true for n = k
- Add (k+1) to both sides
- Simplify to (k+1)(k+2)/2
- State that the claim holds for all n
Questions people ask
Why do I need the base case in induction?
The step only says 'if it works for k, it works for k + 1'. Without a starting point, nothing is ever true to begin the chain. A false claim such as 'n = n + 1' passes the step but fails at the base case, so both parts are required.
What is the inductive hypothesis?
It is the assumption that the claim is true for n = k, for one fixed but arbitrary k. You do not prove it. You use it to show the claim for k + 1. In the sum formula, you replace 1 + ... + k with k(k + 1)/2 during that step.