Induction / Basics
Least You Need to Know: Induction Basics
Mathematical induction proves a statement for every integer in a sequence by checking a starting case and then linking one case to the next.
The least you need to know
- Induction has a base case and an inductive step.
- In the inductive step, assume the claim is true for n = k.
- Then prove the claim for n = k+1.
- The induction hypothesis is a temporary assumption used only inside the inductive step.
- A correct algebraic target matters as much as the algebra itself.
Key notation
P(n)
the statement being proved
P(1)
base case at n = 1
P(k)
induction hypothesis
P(k+1)
next case to prove
Tiny worked example
- Claim: 1 + 2 + ... + n = n(n+1)/2.\n- Base case: n=1 gives 1 = 1(2)/2.\n- Inductive step: assume 1+...+k = k(k+1)/2, then add k+1 to both sides and simplify to (k+1)(k+2)/2.
Common mistakes
- Students often assume P(k+1) instead of proving it.
- Students often forget to check the base case.
- Students often use the induction hypothesis in the wrong place.
How to recognize this kind of problem
- Look for statements claimed for every integer n starting at some base value.
- If the formula changes predictably with n, induction is often a good fit.
- Write the exact target for P(k+1) before manipulating algebra.