See here to learn about Mathematical Induction.

Induction over the natural numbers generally works as follows.

  • First prove the statement $\mathcal{S}(n \in \mathbb{N})$ for the base case, which is usually $n=1$.
  • Next, assume that the statement is true for an input $n$. Then, prove that it is true for the input $n+1$.
history | show excerpt | excerpt history