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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Induction for Inequalities.
Least You Need to Know: Induction for InequalitiesRelated lessons
Keep going with nearby lessons in the same topic.