Discrete Math › Section E · Sequences › Topic E.5
Proof by induction
Checking a formula for a few values of n is evidence, not proof. Mathematical induction turns two finite checks, a starting case and a single general step, into a proof for infinitely many values of n at once.
In this topic
- From patterns to proofs
- The principle of induction
- Writing an induction proof
- Worked example: the sum of the squares
- Worked example: a divisibility proof
- Worked example: an inequality with a later start
- Proving a recurrence's closed formula
- Why induction is valid
- Induction in computing: loop invariants
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…