Principle of strong induction and logical equivalence

Reduction to ordinary induction: Given a predicate $P(n)$ for $n \ge n_0$, define the cumulative conjunction $Q(n) \equiv P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$. At the base index $n = n_0$, the conjunction $Q(n_0)$ has a single term $P(n_0)$, which holds by the strong base case hypothesis.

**Inductive step for $Q(k)$:** Fix an integer $k \ge n_0$ and assume $Q(k)$ is true. By definition of $Q(k)$, all statements $P(n_0), P(n_0+1), \dots, P(k)$ are true. The strong inductive hypothesis $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ then implies that $P(k+1)$ is also true.

Conclusion: Combining $Q(k)$ with $P(k+1)$ proves $Q(k+1) \equiv Q(k) \wedge P(k+1)$. By the ordinary principle of mathematical induction applied to $Q(n)$, the statement $Q(n)$ holds for every integer $n \ge n_0$; in particular, its last conjunct $P(n)$ holds for all $n \ge n_0$.