强归纳法原理及其逻辑等价性

归结为普通归纳法： 给定关于 $n \ge n_0$ 的谓词 $P(n)$，定义累积合取命题 $Q(n) \equiv P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$。在起始指标 $n = n_0$ 处，$Q(n_0)$ 仅含单项 $P(n_0)$，由强归纳法的奠基假设知其成立。

**关于 $Q(k)$ 的归纳步：** 固定整数 $k \ge n_0$ 并假设 $Q(k)$ 为真。由 $Q(k)$ 的定义知 $P(n_0), P(n_0+1), \dots, P(k)$ 全部为真。于是由强归纳步假设 $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ 推出 $P(k+1)$ 也为真。

结论： 将 $Q(k)$ 与 $P(k+1)$ 结合即得 $Q(k+1) \equiv Q(k) \wedge P(k+1)$。对命题 $Q(n)$ 应用普通数学归纳法可知，对所有整数 $n \ge n_0$ 均有 $Q(n)$ 成立；特别地，其最后一个合取项 $P(n)$ 对所有 $n \ge n_0$ 都成立。