Induction

Book: A Walk through Combinatorics

Mathematical induction is a method to prove statements. Two steps:

1. Initial step: Prove that the statement is true for the smallest value of $m$ for which it is defined, usuaully 0 or 1.
2. The Induction step: Prove that from the fact that the statement is true for $n$ ("the induction hypothesis"), it follows that the statement is also true for $n+1$.

---

Children

1. Number of Subsets of [n] is 2^n
2. Strong Induction

---

Backlinks

• Divisible by Six
• Tennis Defeated (Induction)