Nguyên lý quy nạp mạnh và sự tương đương logic

Đưa về quy nạp thường: Cho vị từ $P(n)$ với $n \ge n_0$, định nghĩa mệnh đề hội tích lũy $Q(n) \equiv P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$. Tại chỉ số cơ sở $n = n_0$, mệnh đề $Q(n_0)$ chỉ có một hạng tử $P(n_0)$, đúng theo giả thiết cơ sở của quy nạp mạnh.

**Bước quy nạp cho $Q(k)$:** Cố định số nguyên $k \ge n_0$ và giả sử $Q(k)$ đúng. Theo định nghĩa của $Q(k)$, tất cả các mệnh đề $P(n_0), P(n_0+1), \dots, P(k)$ đều đúng. Giả thiết bước quy nạp mạnh $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ khi đó suy ra $P(k+1)$ cũng đúng.

Kết luận: Kết hợp $Q(k)$ với $P(k+1)$ ta chứng minh được $Q(k+1) \equiv Q(k) \wedge P(k+1)$. Áp dụng nguyên lý quy nạp toán học thông thường cho $Q(n)$, mệnh đề $Q(n)$ đúng với mọi số nguyên $n \ge n_0$; nói riêng, hạng tử cuối $P(n)$ đúng với mọi $n \ge n_0$.