Proof / Induction Basics
Least You Need to Know: Induction Basics
Mathematical induction proves a statement for every integer in a sequence by establishing a base case and an induction step.
Least you need to know
- Start by proving the base case.
- State the induction hypothesis clearly for k.
- Use the induction hypothesis to prove the case k+1.
- Do not assume the statement for k+1.
- Induction is a chain: base case starts it, induction step keeps it going.
Key notation
- P(n) — the statement at integer n
- k — an arbitrary integer in the induction step
- k+1 — the next case to prove
Worked example
- To prove 1 + 2 + ... + n = n(n+1)/2, first check n = 1.\n- Then assume it is true for n = k.\n- Replace 1 + 2 + ... + k with k(k+1)/2 and add k+1.\n- Simplify to get (k+1)(k+2)/2.
Common mistakes
- Students often skip the base case.
- Students often assume the statement they are supposed to prove for k+1.
- Students often forget to use the induction hypothesis explicitly.
How to recognize it
- Induction is common when the statement is indexed by n.
- Look for formulas involving sums, divisibility, or recurrence-like patterns.
- If the statement says for all integers n greater than or equal to some start value, induction may fit.
Next recommended lesson
Continue through this topic with Least You Need to Know: Proof by Cases.
Least You Need to Know: Proof by CasesRelated lessons
Keep going with nearby lessons in the same topic.