Theorem 0.3.6 (Principle of induction). Let $P(n)$ be a statement depending on a natural number $n$. Suppose that 1. (basis statement) $P(1)$ is true, 2. (induction step) if $P(n)$ is true, then $P(n+1)$ is true. Then $P(n)$ is true for all $n \in \mathbb{N}$. #### Proof Suppose $S$ is the set of [[Natural Number|natural numbers]] $m$ for which $P(m)$ is not true. Suppose $S$ is [[‡ nonempty]]. Then $S$ has a least [[Element of a Set|element]] by the [[Well Ordering Property]]. Let us call $m$ the least element of $S$. We know $1 \notin S$ by assumption that the basis statement is satisfied. Therefore $m>1$ and $m-1$ is a natural number as well. Since $m$ is the least element of $S$, we know that $P(m-1)$ is true. But by the induction step we see that $P(m-1+1)=P(m)$ is true, contradicting the statement that $m \in S$. Therefore $S$ is empty and $P(n)$ is true for all $n \in \mathbb{N}$. [[Basic Analysis I - Introduction to real analysis Volume I]]