Primary reference: Chapter 10 (Mathematical Induction) of Book of Proof by Richard Hammack

richardhammack.github.io

Content covered in this unit includes:

• The recipe for proving a statement by induction:

  <aside>

  Proposition. For all $n \in \mathbb{N}$, $P(n)$.

  Proof. We will prove this by induction on $n$.

  Base case. When $n = 1$… [show that $P(1)$ is true]

  Inductive step. Suppose $P(k)$ for some $k \in \mathbb{N}$.

  …

  Therefore $P(k + 1)$.

  We conclude that $P(n)$ for all $n \in \mathbb{N}$.

  </aside>

  This recipe may need to be adjusted if the base case is not $n = 1$, or if multiple base cases are required.