Matematika Diskrit : Prinsip Induksi Kuat

📋 Daftar Isi

Prinsip Induksi Kuat

Kadang-adang diperlukan lebih dari satu hipotesis induksi untuk membuktikan sebuah pernyataan. Untuk itu kita menggunakan prinsip induksi kuat (strongly induction principle).

Misalkan p(n) adalah pernyataan perihal bilangan bulat. Kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ≥ n₀.

Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:

p(n₀) benar, dan
jika p(n₀), p(n₀₊₁), …, p(n) benar maka p(n+1) juga benar untuk semua n ≥ n₀.

Pada poin 2 terdapat lebih dari satu hipotesis, yaitu mengasumsikan p(n₀), p(n₀₊₁), …, p(n) benar.

Latihan Soal

Soal 1

Bilangan bulat positif disebut bilangan prima jika dan hanya jika bilangan bulat tersebut hanya habis dibagi dengan 1 dan dirinya sendiri. Kita ingin membuktikan bahwa setiap bilangan bulat n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Buktikan dengan prinsip induksi kuat.

Penyelesaian:

(i) Basis induksi: Jika n = 2, maka 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri.

(ii) Langkah induksi: Misalkan pernyataan bahwa bilangan 2, 3, …, n dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima adalah benar (hipotesis induksi).

Kita perlu menunjukkan bahwa n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima. Ada dua kemungkinan nilai n + 1:

Jika n + 1 sendiri bilangan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima
Jika n + 1 bukan bilangan prima, maka terdapat bilangan bulat positif a yang membagi habis n + 1 tanpa sisa. Dengan kata lain, (n + 1)/ a = b atau (n + 1) = ab yang dalam hal ini, 2 ≤ a ≤ b ≤ n. Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Ini berarti, n + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n + 1 = ab.

Pada Soal 1, kita membuat hipotesis lebih dari satu, yaitu:

Asumsikan 2 dapat dinyatakan sebagai perkalian bilangan prima
Asumsikan 3 dapat dinyatakan sebagai perkalian bilangan prima
…
Asumsikan n dapat dinyatakan sebagai perkalian bilangan prima

Karena 2 ≤ a ≤ b ≤ n, maka menurut hipotesis induksi di atas a dan b juga dapat dinyatakan sebagai perkalian bilangan-bilangan prima.

Dengan menggunakan banyak hipotesis, maka pembuktian kita menjadi lebih kuat. Jika hanya satu saja hipotesisnya, yaitu mengasumsikan n dapat dinyatakan sebagai perkalian bilangan prima, maka pembuktiannya menjadi kurang kuat.

Soal 2

[LIU85] Teka-teki susun potongan gambar (jigsaw puzzle) terdiri dari sejumlah potongan
(bagian) gambar (lihat Gambar). Dua atau lebih potongan dapat disatukan untuk membentuk potongan yang lebih besar. Lebih tepatnya, kita gunakan istilah blok bagi satu potongan gambar.

Blok-blok dengan batas yang cocok dapat disatukan membentuk blok yang lain yang lebih besar. Akhirnya, jika semua potongan telah disatukan menjadi satu buah blok, teka-teki susun gambar itu dikatakan telah dipecahkan. Menggabungkan dua buah blok dengan batas yang cocok dihitung sebagai satu langkah.

Gunakan prinsip induksi kuat untuk membuktikan bahwa untuk suatu teka-teki susun gambar dengan n potongan, selalu diperlukan n – 1 langkah untuk memecahkan teki itu.

Penyelesaian:

(i) Basis induksi: Untuk teka-teki susun gambar dengan satu potongan, tidak diperlukan langkah apa-apa untuk memecahkan teka-teki itu.

(ii) Langkah induksi: Misalkan pernyataan bahwa untuk teka-teki dengan n potongan (n = 1, 2,3, …, k) diperlukan sejumlah n – 1 langkah untuk memecahkan teka-teki itu adalah benar (hipotesis induksi). Kita harus membuktikan bahwa untuk n + 1 potongan diperlukan n langkah.

Bagilah n + 1 potongan menjadi dua buah blok –satu dengan n₁ potongan dan satu lagi dengan n₂ potongan, dan n₁ + n₂ = n + 1.

Untuk langkah terakhir yang memecahkan teka-teki ini, dua buah blok disatukan sehingga membentuk satu blok besar.

Menurut hipotesis induksi, diperlukan n₁ – 1 langkah untuk menyatukan blok yang satu dan n₂-1 langkah untuk menyatukan blok yang lain.

Digabungkan dengan satu langkah terakhir yang menyatukan kedua blok tersebut, maka banyaknya langkah adalah

( n₁ – 1) + ( n₂ – 1 ) + 1 langkah terakhir = (n₁ + n₂) – 2 + 1 = n + 1 – 1 = n.

Karena langkah (i) dan (ii) sudah diperlihatkan benar maka terbukti bahwa suatu teka-teki susun gambar dengan n potongan, selalu diperlukan n – 1 langkah untuk memecahkan teki-teki itu.