Induksi Matematika — Aturan Penalaran

Bentuk

P(0),\; \forall k\,\bigl(P(k) \to P(k+1)\bigr) \;\;\vdash\;\; \forall n\, P(n)

Premis-premisnya di kiri, dibaca “maka”, dan kesimpulannya di kanan.

Butuh 2 premis.

Kenapa boleh

Dua bagian yang keduanya wajib. Basis: $P(0)$ benar, jadi ada titik awal. Langkah: untuk $k$ sembarang, kalau $P(k)$ benar maka $P(k+1)$ benar. Keduanya bersama berarti $P$ menjalar ke seluruh bilangan asli.

Contoh

Basis: $0 = \frac{0 \cdot 1}{2}$ , benar. Langkah: andaikan $0 + 1 + \dots + k = \frac{k(k+1)}{2}$ . Maka jumlah sampai $k+1$ adalah $\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$ , persis rumusnya untuk $k+1$ . Maka berlaku untuk semua $n$ .

Jebakan

Dua jebakan yang berbeda. Pertama, salah satu bagian sering dilupakan — langkah saja tanpa basis tidak membuktikan apa pun, karena tidak ada yang menjalar. Kedua, di langkahnya kita mengandaikan $P(k)$ ; memakai $P(k+1)$ di sana adalah mengasumsikan yang sedang dibuktikan.

Dipakai di

Belum ada pembuktian yang memakai aturan ini — daftarnya akan terisi sendiri begitu teorema mulai ditulis, karena setiap langkah mencatat aturan yang dipakainya.

Aturan lain di Induksi

Induksi Kuat