Induksi Matematika Fitriyanti Mayasari
Pendahuluan Induksi Matematika merupakan salah satu cara yang dapat digunakan untuk membuktikan pernyataan-pernyataan yang menegaskan bahwa suatu p(n) adalah benar untuk semua bilangan bulan positif, dimana p(n) adalah fungsi proporsional. Contoh p(n) : “Jumlah bilangan bulat positif dari 1 sampai n adalah n(n + 1)/2”. Dibuktikan Buktikan p(n) benar! menggunakan Induksi Matematika
Pengertian Atau dengan kata lain, Induksi Matematika adalah metode pembuktian untuk pernyataan perihal bilangan bulat. Induksi Matematika dapat digunakan untuk membuktikan hasil yang bervariasi dan secara luas digunakan untuk membuktikan hasil dari objek diskrit dengan variasi yang besar Contohnya : Digunakan untuk membuktikan hasil mengenai kompleksitas dari algoritma, kebenaran program komputer tertentu serta teorema mengenai graph dan tree NOTE: Induksi Matematika bukan sebuah tool yang digunakan untuk menemukan formula/teorema baru!!!
Jadi... Induksi Matematika merupakan Teknik Pembuktian yang Baku di dalam matematika Melalui induksi matematika kita dapat mengurangi langkahlangkah pembuktian [bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran] dengan hanya melakukan sejumlah langkah saja.
Prinsip Induksi Sederhana Pembuktian menggunakan Induksi Matematika memiliki 2 bagian : 1. Menunjukkan bahwa statement mengandung bilangan bulat positif pertama Basic Step 2. Menunjukkan bahwa jika statement mengandung sebuah bilangan bulat positif, maka statement tersebut juga memuat bilangan bulat yang lebih besar berikutnya Induction Step Misalkan p(n) adalah pernyataan perihal bilangan bulat positif dan ingin dibuktikan bahwa p(n) adalah benar untuk semua bilangan bulat positif n. Untuk membuktikan pernyataan ini, kita hanya perlu menunjukkan bahwa : 1. p(1) benar, dan 2. Jika p(k) benar maka p(k+1) juga benar, untuk semua bilangan bulat positif n 1
Prinsip Induksi Sederhana Basic Step
Pembuktian p(1) Benar
Induction Step
Pembuktian Jika p(k) benar, maka p(k+1) adalah benar
Berisi asumsi yang menyatakan bahwa p(k) benar. Asumsi ini disebut Hipotesis Induksi Jika kedua langkah tersebut benar, maka sudah terbukti bahwa p(n) benar untuk semua bilangan bulat positif n
Prinsip Induksi Sederhana Basic Step
Benar Benar
Induction Step
Benar
Contoh Prinsip Induksi Sederhana Efek Domino 1
2
3
4
5
k
K+1
Contoh Soal 1 Gunakan induksi matematik untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n2. Penyelesaian 1 + 3 + 5 + … + (2n – 1) = n2 [catatlah bahwa bilangan ganjil positif ke-n adalah (2n – 1)]. (i) Basic Step : Untuk n = 1, Jumlah satu buah bilangan ganjil positif pertama adalah 12 = 1. BENAR Karena jumlah satu buah bilangan ganjil positif pertama adalah 1.
(ii) Induction Step : Andaikan Saat n = k, pernyataan 1 + 3 + 5 + … + (2k – 1) = k2 adalah benar (hipotesis induksi) Saat n = k+1 1 + 3 + 5 + … + (2k – 1) + (2k + 1) = (k + 1)2 juga benar. dibuktikan sebagai berikut :
1 + 3 + 5 +..+ (2k – 1) + (2k + 1) = [1 + 3 + 5 +..+ (2k – 1)] + (2k + 1) = k2 + (2k + 1) = k2 + 2k + 1 = (k + 1)2
Karena Basic Step dan Induction Step keduanya telah diperlihatkan benar, maka jumlah n buah bilangan ganjil positif pertama adalah n2.
Prinsip Induksi yang dirampatkan Misalkan p(n) adalah pernyataan perihal bilangan bulat dan ingin dibuktikan bahwa p(n) adalah benar untuk semua bilangan bulat nn0. Untuk membuktikan pernyataan ini, kita hanya perlu menunjukkan bahwa : 1. 2.
p(n0) benar, dan Jika p(k) benar maka p(k+1) juga benar, untuk semua bilangan bulat positif n n0
Prinsip Induksi yang dirampatkan Basic Step
Benar Benar
Induction Step
Benar
Contoh Soal 2 Untuk semua bilangan bulat tidak negatif n, Buktikan dengan induksi matematika bahwa : 20 + 21 + 22 + ... + 2n = 2n+1 – 1 Penyelesaian 20 + 21 + 22 + ... + 2n = 2n+1 – 1 (i) Basic Step : Untuk n = 0, bilangan bulat tidak negatif pertama
Maka p(n0) adalah benar
(ii) Induction Step : Andaikan Saat n = k, pernyataan 20 + 21 + 22 + … + 2k = 2k+1 – 1 adalah benar (hipotesis induksi) Saat n = k+1 20 + 21 + 22 + … + 2k + 2k+1= 2k+2 – 1 harus ditunjukkan benar. dibuktikan sebagai berikut : 20 + 21 + 22 + … + 2k + 2k+1 = (20 + 21 + 22 + … + 2k ) + 2k+1 = (2k+1 – 1) + 2k+1 = (2. 2k+1 ) – 1 = (21 . 2k+1) – 1 = 2k+2 – 1 Karena langkah 1 dan 2 keduanya telah diperlihatkan benar, maka untuk semua bilangan bulat tidak-negatif n, terbukti bahwa 20 + 21 + 22 + … + 2n = 2n+1 – 1
Prinsip Induksi Kuat Misalkan p(n) adalah pernyataan perihal bilangan bulat dan ingin dibuktikan bahwa p(n) adalah benar untuk semua bilangan bulat nn0. Untuk membuktikan pernyataan ini, kita hanya perlu menunjukkan bahwa : 1. 2.
p(n0) benar, dan Jika p(n0), p(n0+1), ..., p(k) benar maka p(k+1) juga benar, untuk semua bilangan bulat positif n n0
Prinsip Induksi Kuat Benar
Basic Step Induction Step
Benar
Benar
Contoh Soal 3 Bilangan bulat positif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi 1 dan dirinya sendiri. Ingin dibuktikan bahwa setiap bilangan bulat positif n(n2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Buktikan dengan prinsip induksi kuat Penyelesaian (i) Basic Step : Jika n = 2, maka 2 adalah bilangan prima dan dinyatakan sebagai perkalian dari 1 buah bilangan prima, yaitu dirinya sendiri
(ii) Induction Step : Misalkan pernyataan bahwa bilangan 2, 3,..., k dinyatakan sebagai perkalian (satu atau lebih) bilangan prima adalah benar Hipotesis Induksi Perlu dibuktikan bahwa k + 1 juga dapat dinyatakan sebagai perkalian bilangan prima. Ada 2 kemungkinan nilai k + 1 : 1. Jika k + 1 adalah bilangan prima 2. Jika k + 1 bukan bilangan prima, maka terdapat bil. Bulat positif a yang membagi habis k+1 tanpa sisa, atau : (n + 1)/ a = b atau (n + 1) = ab yang dalam hal ini : 2 a b n menurut hipotesis induksi, a & b dapat dinyatakan sebagai perkalian 1 atau lebih bil prima. Sehingga k + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena k + 1 adalah ab
Karena langkah (i) dan (ii) sudah ditunjukkan benar, maka terbukti bahwa setiap bilangan bulat positif n (n 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.
Latihan Soal 1. Untuk semua n 1, buktikan dengan induksi matematik bahwa n3+2n adalah kelipatan 3. 2. Buktikan bahwa 22n-1 habis dibagi 3 untuk semua bilangan bulat n 1.
