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 mm for which it is defined, usuaully 0 or 1.
  2. The Induction step: Prove that from the fact that the statement is true for nn ("the induction hypothesis"), it follows that the statement is also true for n+1n+1.

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