Materi MatDis (Matematika Diskret) : Induksi Matematika

Metode pembuktian untuk proposisi perihal bilangan bulat adalah induksi matematika. Induksi matematika merupakan teknik pembuktian yang baku di dalam matematika. Melalui induksi matematika kita dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas. Proposisi Perihal Bilangan Bulat Proposisi ini mengkaitkan suatu masalah yang dihubungkan dengan bilangan bulat. Contoh : Kita ingin menemukan rumus jumlah dari n buah bilangan ganjil positif yang pertama. Misalnya untuk n = 1, 2, 3, 4, 5, kita mengamati jumlah n bilangan ganjil positif pertama adalah n = 1 → 1 = 1 n = 2 → 1 + 3 = 4 n = 3 → 1 + 3 + 5 = 9 n = 4 → 1 + 3 + 5 + 7 = 16 n = 5 → 1 + 3 + 5 + 7 + 9 = 25 Setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Untuk semua n ≥ 1, n3 + 2n adalah kelipatan 3. Untuk membayar biaya pos sebesar n sen dolar (n ≥ 8) selalu dapat digunakan hanya perangko 3 sen dan 5 sen dolar. Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lainnya hanya sekali. Jika ada n orang tamu maka jumlah jabat tangan yang terjadi adalah n(n – 1)/2 . Banyaknya himpunan bagian yang dapat dibentuk dari sebuah himpunan yang beranggotakan n elemen adalah 2n. Proposisi – proposisi semacam di ataslah yang dapat dibuktikan dengan induksi matematika. Cara pembuktian dengan induksi matematika : Prinsip Induksi Sederhana Prinsip induksi sederhana berbunyi sebagai berikut : Misalkan p(n) adalah proposisi perihal bilangan bulat positif dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Untuk membuktikan proposisi ini, kita hanya perlu menunjukkan bahwa : p(1) benar, dan jika p(n) benar, maka p(n + 1) juga benar untuk setiap n ≥ 1. Sehingga p(n) benar untuk semua bilangan bulat positif n. 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 menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Basis induksi digunakan untuk memperlihatkan bahwa pernyataan tersebut benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil. Kemudian kita harus memperlihatkan bahwa implikasi p(n) → p(n + 1) benar untuk setiap bilangan bulat positif. Untuk membuktikan implikasi tersebut benar untuk setiap bilangan bulat positif n, kita perlu menunjukkan bahwa p(n + 1) tidak mungkin salah bila p(n) benar. Hal ini diselesaikan dengan cara memperlihatkan bahwa berdasarkan hipotesis p(n) benar maka p(n + 1) juga harus benar. Perhatikan bahwa dalam induksi matematika kita tidak mengasumsikan bahwa p(n) benar untuk semua bilangan bulat positif. Kita hanya memperlihatkan bahwa jika diasumsikan p(n) benar, maka p(n + 1) juga benar untuk setiap n positif. Pembuktian dengan induksi matematika mirip dapat kita ilustrasikan dengan fenomena yang dikenal dengan efek domino. Sejumlah batu domino diletakkan berdiri dengan jarak ruang yang sama satu sama lain. Untuk merebahkan semua batu domino, kita hanya perlu mendorong domino 1 ke kanan. Jika domino 1 di dorong ke kanan, ia akan mendorong domino 2, domino 2 mendorong domino 3, begitu seterusnya sehingga semua batu domino rebah ke kanan. Contoh : Tunjukkan bahwa untuk n ≥ 1, 1 + 2 + 3 + ... + n = n (n + 1) / 2 melalui induksi matematika. Penyelesaian : Andaikan bahwa p(n) menyatakan proposisi bahwa untuk n ≥ 1, 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 : Basis induksi : p(1) benar, karena untuk n = 1 kita peroleh 1 = 1 (1 + 1) / 2 = 1 (2) / 2 = 2/2 = 1 Langkah induksi : Misalkan p(n) benar, yaitu mengasumsikan 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) = (1 + 2 + 3 + ... + n) + (n + 1) = [n (n + 1)/2 ] + (n + 1) = [ (n2 + n)/2 ] + (n + 1) = [ (n2 + n )/2 ] + [ (2n + 2)/2 ] = (n2 + 3n + 2)/2 = (n + 1)(n + 2)/2 = (n + 1) [ (n + 1) + 1]/2 Karena langkah (a) dan (b) tealh dibuktikan benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ≥ 1, 1 + 2 + 3 + ... + n = n (n + 1)/2. Prinsip Induksi yang Dirampatkan 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, dan jika p(n) benar maka p(n + 1) benar untuk setiap n ≥ n0, sehingga p(n) benar untuk semua bilangan bulat n ≥ n0. Contoh : Buktikan dengan induksi matematika bahwa 3n < n! Untuk n bilangan bulat positif yang lebih besar dari 6. Penyelesaian : Misalkan p(n) adalah proposisi bahwa 3n < n! Untuk n bilangan bulat positif yang lebih besar dari 6. Basis induksi : p(7) benar, karena 37 = 2187 dan 7! = 5040 Langkah induksi : Misalkan bahwa p(n) benar, yaitu asumsikan bahwa 3n < n! Adalah benar. Kita harus menunjukkan bahwa p(n + 1) juga benar, yaitu 3n+1 < (n + 1)!. Hal ini ditunjukkan sebagai berikut : 3n+1 < (n+1)! 3.3n < (n+1) . n! 3n . 3/(n+1) < n! Menurut hipotesis induksi, 3n < n!, sedangkan untuk n > 6, nilai 3?(n+1) < 1, sehingga 3/(n+1) akan memperkecil nilai di ruas kiri persamaan. Efek nettonya, 3n . 3/(n+1) < n! Jelas benar. Karena langkah (a) dan (b) sudah ditunjukkan benar, maka terbukti bahwa 3n < n! untuk n bilangan bulat positif lebih besar dari 6. Prinsip Induksi Kuat 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, dan jika p(n0), p(n0+1), ..., p(n) benar, maka p(n+1) juga benar untuk setiap bilangan bulat n ≥ n0, sehingga p(n) benar untuk semua bilangan bulat n ≥ n0. Versi induksi yang lebih kuat ini mirip dengan induksi sederhana, kecuali bahwa pada langkah 2 kita mengambil hipotesis induksi yang lebih kuat bahwa semua pernyataan p(1), p(2), ..., p(n) adalah benar daripada hipotesis yang menyatakan bahwa p(n) benar (pada induksi sederhana). Prinsip induksi kuat memungkinkan kita mencapai kesimpulan yang sama meskipun memberlakukan andaian yang lebih banyak. Contoh : Bilangan bulat positif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri. Kita ingin membuktikan bahwa setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih ) bilangan prima. Buktikan dengan prinsip induksi kuat. Penyelesaian : Misalkan p(n) adalah proposisi bahwa setiap bilangan bulat positif n (n ≥ 2 ) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Basis induksi : p(2) benar, karena 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri. Langkah induksi. Misalkan p(n) benar, yaitu asumsikan bahwa bilangan 2, 3, ..., n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima (hipotesis induksi). Kita perlu menunjukkan bahwa p(n + 1) benar, yaitu n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima. Hal ini ditunjukkan sebagai berikut : 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. Karena langkah (a) dan (b) sudah ditunjukkan benar, maka terbukti bahwa setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Bentuk Induksi Secara Umum Bentuk induksi secara umum dapat dituliskan sebagai berikut : Misalkan X terurut dengan baik oleh “<”, dan p(x) adalah pernyataan perihal elemen x dari X. Kita ingin membuktikan bahwa p(x) benar untuk semua x ∈ X. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa: p(x0) benar, yang dalam hal ini x0 adalah elemen terkecil di dalam X, dan jika p(y) benar untuk y < x, maka p(x) juga benar untuk setiap x > x0 di dalam X, sehingga p(x) benar untuk semua x ∈ X. TUGAS : Buktikan bahwa : 1. p(n) : 1 + 4 + 7 + ... + (3n – 2) = (n (3n-1))/2 2. p(n) : 1 + 2 + 22 + 23 + ... + 2n = 2n+1 – 1 3. p(n) : 1.2 + 2.3 + 3.4 + ... + n (n+1) = ([n(n+1)(n+2)])/3 Penyelesaian : 1. p(n) : 1 + 4 + 7 + ... + (3n – 2) = (n (3n-1))/2 p(n+1) : 1 + 4 + 7 + ... + (3n – 2) + (3(n+1)-2) = ((n+1)(3(n+1)-1))/2 (n (3n-1))/2 + (3n+3-2) = ((n+1)(3n+3-1))/2 (n (3n-1))/2 + (3n +1) = ((n+1)(3n+2))/2 (n (3n-1)+2(3n+1))/2 = ((n+1)(3n+2))/2 (3n^2-n+6n+2)/2 = ((n+1)(3n+2))/2 (3n^2+5n+2)/2 = ((n+1)(3n+2))/2 ((3n+2)(n+1))/2 = ((n+1)(3n+2))/2 TERBUKTI 2. p(n) : 1 + 2 + 22 + 23 + ... + 2n = 2n+1 – 1 p(n+1) : 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = (1 + 2 + 22 + 23 + ... + 2n ) + 2n+1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = ( 2n+1 – 1 ) + 2n+1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = ( 2n+1 + 2n+1 ) - 1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = ( 2 . 2n+1 ) - 1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = 2n+2 -1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = 2(n+1)+1 - 1 1 + 2 + 22 + 23 + ... + 2n = 2n+1 – 1 TERBUKTI 3. p(n) : 1.2 + 2.3 + 3.4 + ... + n (n+1) = ([n(n+1)(n+2)])/3 p(n+1) : 1.2 + 2.3 + 3.4 + ... + n (n+1) + (n+1)+(n+1+1) = ([(n+1)(n+2)(n+3)])/3 ([n(n+1)(n+2)])/3 + (n+1)(n+2) = ([(n+1)(n+2)(n+3)])/3 (n[(n+1)(n+2)]=3[(n+1)(n+2)])/3 = ([(n+1)(n+2)(n+3)])/3 ((n+1)(n+2)(n+3))/3 = ([(n+1)(n+2)(n+3)])/3 TERBUKTI