📋 Daftar Isi
Prinsip Induksi Sederhana
Misalkan p(n) adalah pernyataan perihal bilangan bulat positif. Kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Untuk membuktikan pernyataan ini, kita hanya perlu menunjukkan bahwa:
- p(1) benar
- jika p(n) benar, maka p(n + 1) juga benar, untuk setiap n ≥ 1
Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah induksi. Langkah induksi berisi asumsi (andaian) yang menyatakan bahwa p(n) benar. Asumsi tersebut dinamakan hipotesis induksi.
Bila kita sudah bisa menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.
Induksi matematik berlaku seperti efek domino. Untuk merobohkan semua domino, cukup mendorong domino pertama. Domino pertama akan mendorong domino kedua. Domino kedua akan mendorong domino ketiga, demikian seterusnya.
Contoh Pembuktian Pertama
Contoh 1
Buktikan bahwa jumlah n bilangan bulat positif pertama adalah n(n + 1)/2.
Penyelesaian:
Misalkan p(n) menyatakan proposisi bahwa jumlah n bilangan bulat positif pertama adalah n(n+1)/2 , yaitu
1 + 2 + 3 + … + n = n(n + 1)/2
Kita harus membuktikan kebenaran proposisi ini dengan dua langkah induksi sebagai berikut:
(i) Basis induksi: p(1) benar, karena untuk n = 1 kita peroleh
1 = 1(1 + 1)/ 2
= 1(2)/ 2
= 2/2
= 1
(ii) Langkah induksi: Misalkan p(n) benar, yaitu asumsikan bahwa
1 + 2 + 3 + … + n = n(n + 1)/2 adalah benar (hipotesis induksi).
Kita harus memperlihatkan bahwa p(n + 1) juga benar, yaitu
1 + 2 + 3 + … + n+(n+1) = (n + 1)[(n + 1) + 1]/2
Untuk membuktikan ini, tunjukkan bahwa
1 + 2 + 3 + … + n + (n + 1)= (1 + 2 + 3 + … + n) + (n +1)
= [n (n + 1)/2 ] + (n + 1)
= (n + 1) [n/2 + 1]
= (n + 1) + [n/2 + 2/2]
= (n + 1) (n + 2)/2
= (n + 1) [(n + 1) + 1]/2
Karena langkah (i) dan (ii) telah dibuktikan benar, maka terbukti bahwa untuk semua bilangan bulat positif n, 1 + 2 + 3 + … + n = n(n + 1)/2.
Contoh 2
Gunakan induksi matematik untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n2
Penyelesaian:
(i) Basis induksi: Untuk n = 1, jumlah satu buah bilangan ganjil positif pertama adalah 1= 12. Ini benar karena jumlah satu buah bilangan ganjil positif pertama adalah 1.
(ii) Langkah induksi: Andaikan p(n) benar, yaitu pernyataan
1 + 3 + 5 + … + (2n – 1) = n2
adalah benar (hipotesis induksi) [catatlah bahwa bilangan ganjil positif ke-n adalah (2n – 1)]. Kita harus memperlihatkan bahwa p(n +1) juga benar, yaitu
1 + 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)2 juga benar.
Hal ini dapat kita tunjukkan sebagai berikut:
1 + 3 + 5 + … + (2n – 1) + (2n + 1) = [1 + 3 + 5 + … + (2n – 1)] + (2n + 1) = n2 + (2n + 1)
= n2 + 2n + 1
= (n + 1)2
Karena langkah basis dan langkah induksi keduanya telah diperlihatkan benar, maka jumlah n buah bilangan ganjil positif pertama adalah n2.
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.
