Induksi

Induksi Kuat

Strong induction (complete induction)

Bentuk

\forall k\,\Bigl(\bigl(\forall j < k\; P(j)\bigr) \to P(k)\Bigr) \;\;\vdash\;\; \forall n\, P(n)

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

Butuh 1 premis.

Kenapa boleh

Induksi biasa hanya memberi $P(k)$ untuk membuktikan $P(k+1)$ . Di sini andaikan $P$ benar untuk semua $j < k$ sekaligus, lalu buktikan $P(k)$ . Lebih longgar, dan sama sahnya.

Contoh

Setiap bilangan bulat $n > 1$ punya faktorisasi prima. Untuk $n$ , kalau $n$ prima selesai; kalau tidak, $n = ab$ dengan $a, b < n$ , dan keduanya sudah punya faktorisasi prima menurut andaian.

Jebakan

Cakupannya harus benar-benar “semua yang di bawah $k$ ”. Kalau kasusnya bergantung pada $k - 2$ , induksi biasa tidak cukup dan yang dibutuhkan induksi kuat — memaksakan yang biasa akan meninggalkan lubang di kasus $k$ yang kecil.

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 Matematika