📋 Daftar Isi
Prinsip Induksi yang Dirampatkan
Prinsip induksi sederhana hanya bisa dipakai untuk n ≥ 1. Untuk sembarang n ≥ n0 kita menggunakan prinsip induksi yang dirampatkan (generalized induction principle).
Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ≥ n0. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:
- p(n0) benar
- jika p(n) benar maka p(n+1) juga benar, untuk semua bilangan bulat n ≥ n0
Contoh 1
Untuk semua bilangan bulat tidak-negatif n, buktikan dengan induksi matematik bahwa 20 + 21 + 22 + … + 2n = 2n+1-1
Penyelesaian:
(i) Basis induksi: Untuk n = 0 (bilangan bulat tidak negatif pertama), kita peroleh 20 = 20+1 – 1.
Ini jelas benar, sebab 20 = 1 = 20+1 – 1
= 21 – 1
= 2 – 1
= 1
(ii) Langkah induksi: Andaikan bahwa p(n) benar, yaitu 20 + 21 + 22 + … + 2n = 2n+1-1
adalah benar (hipotesis induksi). Kita harus menunjukkan bahwa p(n +1) juga benar, yaitu
20 + 21 + 22 + … + 2n + 2n+1 = 2(n+1) + 1-1
juga benar. Ini kita tunjukkan sebagai berikut:
20 + 21 + 22 + … + 2n + 2n+1 = (20 + 21 + 22 + … + 2n) + 2n+1
= (2n+1 – 1) + 2n+1 (hipotesis induksi)
= (2n+1 + 2n+1) – 1
= (2 . 2n+1) – 1
= 2n+2-1
= 2(n+1) + 1 – 1
Karena langkah (i) dan (ii) keduanya telah diperlihatkan benar, maka untuk semua bilangan bulat tidak negatif n, terbukti bahwa 20 + 21 + 22 + … + 2n = 2n+1 -1
Contoh 2
Untuk semua n ≥ 1, buktikan dengan induksi matematik bahwa n3 + 2n adalah kelipatan 3.
Penyelesaian:
(i) Basis induksi: Untuk n = 1, maka 13 + 2(1) = 3 adalah kelipatan 3. Jadi, p(1) benar.
(ii) Langkah induksi: Misalkan p(n) benar, yaitu proposisi n3 + 2n adalah kelipatan 3 (hipotesis induksi). Kita harus memperlihatkan bahwa p(n + 1) juga benar, yaitu (n + 1)3 + 2(n + 1) adalah kelipatan 3.
Hal ini dapat kita tunjukkan sebagai berikut:
(n + 1)3 + 2(n + 1) = (n3 + 3n2 + 3n+1) + (2n + 2)
= (n3 + 2n) + 3n2 + 3n + 3
= (n3 + 2n) + 3(n2 + n + 1)
Perhatikan bahwa:
- (n3 + 2n) adalah kelipatan 3 (dari hipotesis induksi)
- 3(n2 + n + 1) juga kelipatan 3
- maka (n3 + 2n) + 3(n2 + n + 1) adalah jumlah dua buah bilangan kelipatan 3
- sehingga (n3 + 2n)+3(n2 + n + 1) juga kelipatan 3.
Karena langkah (i) dan (ii) sudah diperlihatkan benar, maka terbukti bahwa untuk semua n ≥ 1, n3 + 2n adalah kelipatan 3.
Materi Lengkap
Silakan baca juga beberapa artikel menarik kami tentang Induksi Matematika, daftar lengkapnya adalah sebagai berikut.
Tonton juga video pilihan dari kami berikut ini
Sumber: Materi Kuliah Matematika Diskrit Dr. Ir. Rinaldi Munir, MT.
