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.
The 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
Tiny 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 this kind of problem
- 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.