[proofplan] We reduce strong induction to [ordinary induction](/pages/mathematical-induction) by replacing $P(n)$ with the auxiliary assertion that $P$ holds for every predecessor of $n$. The base case follows from $P(1)$ and the fact that $1$ is the least natural number. The inductive step uses the strong-induction hypothesis in the theorem statement to pass from all predecessors up to $n$ to the next value $P(n+1)$, thereby proving the auxiliary assertion at $n+1$. Ordinary induction then gives the auxiliary assertion for every $n$, and hence $P(n)$ for every $n \in \mathbb{N}$. [/proofplan] [step:Bundle all predecessor assertions into one ordinary induction property] Define an auxiliary property $Q(n)$, for $n \in \mathbb{N}$, by \begin{align*} Q(n) \quad \Longleftrightarrow \quad P(m) \text{ holds for every } m \in \mathbb{N} \text{ with } m \le n. \end{align*} It is enough to prove $Q(n)$ for every $n \in \mathbb{N}$, because then, for each fixed $n \in \mathbb{N}$, the inequality $n \le n$ gives $P(n)$ from $Q(n)$. [/step] [step:Prove the bundled base case from $P(1)$] By hypothesis (i), $P(1)$ holds. If $m \in \mathbb{N}$ and $m \le 1$, then $m = 1$, since $\mathbb{N}$ starts at $1$. Hence $P(m)$ holds for every $m \in \mathbb{N}$ with $m \le 1$, which is exactly $Q(1)$. [/step] [step:Use the strong induction premise to advance the bundled property] Assume $n \in \mathbb{N}$ and assume $Q(n)$ holds. By the definition of $Q(n)$, $P(m)$ holds for every $m \in \mathbb{N}$ with $m \le n$. Hypothesis (ii), applied to this $n$, therefore gives $P(n+1)$. Now let $m \in \mathbb{N}$ satisfy $m \le n+1$. If $m \le n$, then $P(m)$ holds by $Q(n)$. If $m \nleq n$, then, since $m \le n+1$ and $m,n \in \mathbb{N}$, we have $m = n+1$, so $P(m)$ holds by the preceding paragraph. Thus $P(m)$ holds for every $m \in \mathbb{N}$ with $m \le n+1$, which is $Q(n+1)$. [guided] We prove the ordinary-induction implication $Q(n) \implies Q(n+1)$. Fix $n \in \mathbb{N}$ and assume $Q(n)$ holds. By definition, \begin{align*} Q(n) \quad \Longleftrightarrow \quad P(m) \text{ holds for every } m \in \mathbb{N} \text{ with } m \le n. \end{align*} Therefore the antecedent in hypothesis (ii) is satisfied for this value of $n$. Hypothesis (ii) says that whenever $P(m)$ holds for all $m \le n$, the next assertion $P(n+1)$ holds. Hence $P(n+1)$ holds. It remains to verify that this gives the whole bundled assertion $Q(n+1)$, not only the new endpoint. Let $m \in \mathbb{N}$ be any natural number with $m \le n+1$. There are two cases. If $m \le n$, then $P(m)$ follows from $Q(n)$. If $m \nleq n$, then $m$ is a natural number satisfying \begin{align*} n < m \le n+1. \end{align*} Because natural numbers are discrete, this forces $m = n+1$. For this value, $P(m)$ is exactly $P(n+1)$, which was proved above. Therefore $P(m)$ holds for every $m \in \mathbb{N}$ with $m \le n+1$, so $Q(n+1)$ holds. [/guided] [/step] [step:Apply ordinary induction and recover the original property] We have proved $Q(1)$ and, for every $n \in \mathbb{N}$, the implication $Q(n) \implies Q(n+1)$. By the ordinary induction axiom for $\mathbb{N}$, equivalently Peano induction, $Q(n)$ holds for every $n \in \mathbb{N}$. For each $n \in \mathbb{N}$, applying $Q(n)$ with $m = n$ gives $P(n)$, since $n \le n$. Therefore $P(n)$ holds for all $n \in \mathbb{N}$. [/step]