Skip to main content

💪 Prinsip Induksi Kuat

Dalam beberapa kasus, pendekatan induksi biasa belum cukup kuat untuk membuktikan suatu pernyataan matematika. Di sinilah kita membutuhkan versi yang lebih mantap: prinsip induksi kuat (strong induction).

Prinsip ini masih berbicara tentang pembuktian untuk bilangan bulat, tapi kita mengasumsikan lebih banyak hal benar dalam langkah induksinya.

🧠 Rumus Umum​

Misalkan p(n) adalah pernyataan tentang bilangan bulat, dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ≥ n₀. Maka yang perlu kita tunjukkan adalah:

  1. Basis Induksi: Tunjukkan bahwa p(n₀) benar.
  2. Langkah Induksi: Asumsikan bahwa semua pernyataan p(n₀), p(n₀ + 1), ..., p(n) benar.
    Lalu, tunjukkan bahwa p(n + 1) juga benar.

Jika dua langkah ini berhasil, maka kita bisa menyimpulkan bahwa p(n) benar untuk semua bilangan bulat n ≥ n₀.

🔎 Apa Bedanya dengan Induksi Biasa?​

Perbedaan utamanya ada di langkah induksi.
Pada induksi biasa, kita hanya mengasumsikan bahwa p(n) benar untuk membuktikan p(n + 1).
Sedangkan dalam induksi kuat, kita mengasumsikan bahwa semua pernyataan sebelum n + 1 sudah benar:
p(n₀), p(n₀ + 1), ..., p(n).

Dengan kata lain, kita punya lebih banyak "bahan" atau informasi untuk membuktikan langkah berikutnya.

🧾 Analogi Sederhana​

Bayangkan kamu naik tangga, dan kamu yakin bisa naik ke anak tangga ke-n + 1 asalkan kamu sudah berhasil naik dari anak tangga ke-n₀ sampai ke-n. Jadi kamu tidak hanya mengandalkan satu langkah sebelumnya, tapi semua langkah yang sudah kamu lewati.

📌 Contoh Penggunaan​

Misalkan kita ingin membuktikan bahwa setiap bilangan bulat positif lebih besar dari 1 dapat dituliskan sebagai hasil kali bilangan prima.

Pernyataan ini tidak bisa dibuktikan cukup dengan induksi biasa karena kita perlu informasi dari banyak nilai sebelumnya. Tapi dengan induksi kuat, kita bisa menyusun bukti seperti ini:

  1. Basis: Untuk n = 2, benar karena 2 adalah bilangan prima.
  2. Langkah Induksi: Misalkan semua bilangan dari 2 sampai n dapat dinyatakan sebagai hasil kali bilangan prima.
    Untuk n + 1, ada dua kemungkinan:
    • Jika n + 1 adalah bilangan prima, maka ia sudah merupakan hasil kali itu sendiri.
    • Jika n + 1 bukan bilangan prima, maka ia bisa ditulis sebagai hasil kali dari dua bilangan lebih kecil, dan karena dua bilangan itu lebih kecil dari n + 1, maka secara hipotesis mereka sudah bisa ditulis sebagai hasil kali bilangan prima.

Dengan begitu, n + 1 juga dapat ditulis sebagai hasil kali bilangan prima. ✅

Induksi kuat adalah alat yang sangat berguna, terutama ketika sifat dari suatu bilangan bergantung pada beberapa bilangan sebelumnya — bukan hanya satu.