INDUKSI MATEMATIK1 Metodepembuktianuntukpernyataanperihalbilanganbulat adalah induksi matematik. Contoh :p(n): Jumlah bilangan bulat positif dari 1 sampai n adalah n(n + 1)/2. Buktikan p(n) benar! 2 3 Contoh lainnya:1.Setiapbilanganbulatpositifn(n>2)dapatdinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. 2.Untuk semua n > 1, n3 + 2n adalah kelipatan 3. 3.Untuk membayar biaya pos sebesar n sen dolar (n > 8) selalu dapat digunakan hanya perangko 3 sendan 5 sen dolar. 4.Didalamsebuahpesta,setiaptamuberjabattangandengan tamulainnyahanyasekali.Jikaadanorangtamumaka jumlah jabat tangan yang terjadi adalah n(n +1)/2. 5. Banyaknya himpunan bagian yang dapat dibentuk dari sebuah himpunan yang beranggotakan n elemen adalah 2n Induksimatematikmerupakanteknik pembuktian yang baku di dalam matematika.

Melaluiinduksimatematikkitadapat mengurangilangkah-langkahpembuktian bahwa semua bilangan bulat termasuk ke dalam suatuhimpunankebenarandenganhanya sejumlah langkah terbatas. 4 PRINSIP INDUKSI SEDERHANA. Misalkanp(n)adalahpernyataanperihal bilanganbulatpositifdankitaingin membuktikanbahwap(n)benaruntuk semuabilanganbulatpositifn.Untuk membuktikanpernyataanini,kitahanya perlu menunjukkan bahwa: 1.p(1) benar, dan 2.jika p(n) benar maka p(n + 1) juga benar, untuk semua bilangan bulat positif n > 1, 5 Langkah1dinamakanbasisinduksi, sedangkanlangkah2dinamakanlangkah induksi.

Langkahinduksiberisiasumsi(andaian)yang menyatakan bahwa p(n) benar. Asumsi tersebut dinamakan hipotesis induksi.

Bilakitasudahmenunjukkankedualangkah tersebutbenarmakakitasudahmembuktikan bahwap(n)benaruntuksemuabilanganbulat positif n. 6 Induksi matematik berlaku seperti efek domino. 7 8 Contoh 1. 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 positifpertamaadalah12=1.Inibenarkarenajumlahsatubuah bilangan ganjil positif pertama adalah 1. 9 (ii) Langkah induksi: Andaikan p(n) benar, yaitu pernyataan 1 + 3 + 5 + + (2n 1) = n2 adalahbenar(hipotesisinduksi)[catatlahbahwabilanganganjil positifke-nadalah(2n1)].Kitaharusmemperlihatkanbahwa 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.PRINSIP INDUKSIMisalkanp(n)adalahpernyataanperihal bilanganbulatdankitainginmembuktikan bahwap(n)benaruntuksemuabilangan bulatn>n0.Untukmembuktikanini,kita hanya perlu menunjukkan bahwa: 1. p(n0) benar, dan 2. jika p(n) benar maka p(n+1) juga benar, untuk semua bilangan bulat n > n0, 10 11 Contoh2.Untuksemuabilanganbulattidak-negatifn,buktikan dengan induksi matematik bahwa 20 + 21 + 22 + + 2n = 2n+1 - 1 Penyelesaian: (i)Basisinduksi.Untukn=0(bilanganbulattidaknegatif pertama), kita peroleh:20 = 20+1 1. Ini jelas benar, sebab 20 = 1 = 20+1 1 = 21 1 = 2 1 = 1 12 (ii) Langkah induksi. Andaikan bahwa p(n) benar, yaitu 20 + 21 + 22 + + 2n = 2n+1 - 1 adalahbenar(hipotesisinduksi).Kitaharusmenunjukkan 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+11)+2n+1(hipotesis induksi) =(2n+1 + 2n+1) 1 = (2 . 2n+1) 1 = 2n+2 - 1 = 2(n+1) + 1 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 LATIHAN Contoh3.Buktikandenganinduksimatematik bahwapadasebuahhimpunanberanggotakann elemen,banyaknyahimpunanbagianyangdapat dibentuk dari himpunan tersebut adalah 2n. 13 14 Contoh5.BuktikanpernyataanUntukmembayarbiayapos sebesar n sen (n > 8) selalu dapat digunakan hanya perangko 3 sen dan perangko 5 sen benar. Penyelesaian: (i)Basisinduksi.Untukmembayarbiayapos8sendapat digunakan 1 buah perangko 3 sen dan 1 buah perangka 5 sen saja. Ini jelas benar. 15 (ii)Langkahinduksi.Andaikanp(n)benar,yaituuntuk membayarbiayapossebesarn(n>8)sendapatdigunakan perangko3sendan5sen(hipotesisinduksi).Kitaharus menunjukkanbahwap(n+1)jugabenar,yaituuntukmembayar biayapossebesarn+1senjugadapatmenggunakanperangko3 sendanperangko5sen.Adaduakemungkinanyangperlu diperiksa: (a)Kemungkinanpertama,misalkankitamembayarbiayapos senilai n sen dengan sedikitnya satu perangko 5 sen. Dengan menggantisatubuahperangko5sendenganduabuah perangko 3 sen, akan diperoleh susunan perangko senilai n + 1 sen.(b)Kemungkinankedua,jikatidakadaperangko5senyang digunakan, biaya pos senilai n sen menggunakan perangko 3 sen semuanya. Karena n > 8, setidaknya harus digunakan tiga buah perangko 3 sen. Dengan mengganti tiga buah perangko 3sendengan2buahperangko5sen,akandihasilkannilai perangko n + 1 sen. LATIHAN Contoh6.SebuahATM(AnjunganTunaiMandiri) hanyamenyediakanpecahanuangRp20.000,- danRp50.000,-.Kelipatanuangberapakahyang dapatdikeluarkanolehATMtersebut?Buktikan jawaban anda dengan induksi matematik. 16 PRINSIP INDUKSI KUAT Misalkanp(n)adalahpernyataanperihal bilanganbulatdankitainginmembuktikan bahwap(n)benaruntuksemuabilangan bulatn>n0.Untukmembuktikanini,kita hanya perlu menunjukkan bahwa: 1. p(n0) benar, dan 2.jikap(n0),p(n0+1),,p(n)benarmaka p(n+1)jugabenaruntuksemuabilangan bulatn > n0,. 17 18 Contoh 7. Bilangan bulat positif disebut prima jika dan hanya jika bilanganbulattersebuthabisdibagidengan1dandirinyasendiri. Kita ingin membuktikan bahwa setiap bilangan bulat positif n (n > 2)dapatdinyatakansebagaiperkaliandari(satuataulebih) bilangan prima. Buktikan dengan prinsip induksi kuat. Penyelesaian: Basis induksi. Jika n = 2, maka 2 sendiri adalah bilangan prima dandisini2dapatdinyatakansebagaiperkaliandarisatubuah bilangan prima, yaitu dirinya sendiri. 19 Langkah induksi. Misalkan pernyataan bahwa bilangan 2, 3, , ndapatdinyatakansebagaiperkalian(satuataulebih)bilangan primaadalahbenar(hipotesisinduksi).Kitaperlumenunjukkan bahwan+1jugadapatdinyatakansebagaiperkalianbilangan prima. Ada dua kemungkinan nilai n + 1: (a)Jikan+1sendiribilanganprima,makajelasiadapat dinyatakansebagaiperkaliansatuataulebihbilangan prima.(b)Jikan+1bukanbilanganprima,makaterdapat 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 s a s b s n. Menurut hipotesis induksi, a dan bdapatdinyatakansebagaiperkaliansatuataulebihbilangan prima.Iniberarti,n+1jelasdapatdinyatakansebagaiperkalian bilangan prima, karena n + 1 = 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. Contoh8.[LIU85]Teka-tekisusunpotongangambar (jigsawpuzzle)terdiridarisejumlahpotongan(bagian) gambar(lihatGambar).Duaataulebihpotongandapat disatukan untuk membentuk potonganyang lebih besar. Lebihtepatnya,kitagunakanistilahblokbagisatu potongangambar.Blok-blokdenganbatasyangcocok dapatdisatukanmembentukblokyanglainyanglebih besar.Akhirnya,jikasemuapotongantelahdisatukan menjadisatubuahblok,teka-tekisusungambaritu dikatakantelahdipecahkan.Menggabungkanduabuah blokdenganbatasyangcocokdihitungsebagaisatu langkah.Gunakanprinsipinduksikuatuntuk membuktikanbahwauntuksuatuteka-tekisusun gambardengannpotongan,selaludiperlukann1langkah untuk memecahkan teki-teki itu.20 21 22 Penyelesaian: (i)Basisinduksi.Untukteka-tekisusungambardengansatu potongan,tidakdiperlukanlangkahapa-apauntukmemecahkan teka-teki itu. 23 (ii)Langkahinduksi.Misalkanpernyataanbahwauntukteka-teki dengan n potongan (n = 1, 2, 3, , k) diperlukan sejumlah n 1 langkah untuk memecahkan teka-teki itu adalah benar (hipotesis induksi).Kitaharusmembuktikanbahwauntukn+1potongan diperlukan n langkah. Bagilahn+1potonganmenjadiduabuahbloksatudengann1 potongandansatulagidengann2potongan,dann1+n2=n+1. Untuklangkahterakhiryangmemecahkanteka-tekiini,duabuah blokdisatukansehinggamembentuksatublokbesar.Menuruthipotesisinduksi,diperlukann1-1langkahuntukmenyatukan blokyangsatudann21langkahuntukmenyatukanblokyang lain.Digabungkandenganlangkahterakhiryangmenyatukan kedua blok tersebut, maka banyaknya langkah adalah (n1 1) + (n2 1) + 1 langkah terakhir = (n1 + n2) 2 + 1 = n + 1 1 = n. Karena langkah (i) dan (ii) sudah diperlihatkan benar maka terbukti bahwasuatu teka-teki susun gambar dengan n potongan, selalu diperlukan n - 1 langkah untuk memecahkan teki-teki itu. 24 Contoh 9. Tunjukkan apa yang salah dari pembuktian di bawah ini yang menyimpulkan bahwa semua kuda berwarna sama? MisalkanP(n)adalahpernyataanbahwasemuakudadidalam sebuah himpunan berwarna sama (i)Basisinduksi:jikakudadidalamhimpunanhanyaseekor, jelaslah P(1) benar. (ii)Langkahinduksi:andaikanbahwasemuakudadidalam himpunannekorkudaberwarnasamaadalahbenar.Tinjau untuk himpunan dengan n + 1 kuda; nomori kuda-kuda tersebut dengan1,2,3,,n,n+1.Tinjauduahimpunan,yaitunekor kuda yang pertama (1, 2, n) harus berwarna sama, dan n ekor kuda yang terakhir (2, 3, , n, n+1) juga harus berwarna sama. Karena himpunan n kuda pertama dan himpunan n kuda terakhir beririsan,makasemuan+1kudaharusberwarnasama.Ini membuktikan bahwa P(n+1) benar. 25 Penyelesaian: langkah induksi tidak benar jika n + 1 = 2, sebab dua himpunan(yangmasing-masingberanggotakann=1elemen) tidak beririsan. SOAL LATIHAN 1. JikaA1,A2,,Anmasing-masingadalah himpunan,buktikandenganinduksimatematik hukum De Morgan rampatan berikut: 26 n nA A A A A A= 2 1 2 12. Buktikan dengan induksi matematik bahwa n5 n habis dibagi 5 untuk n bilangan bulat positif. 27 3. Didalamsebuahpesta,setiaptamuberjabat tangandengantamulainnyahanyasekalisaja. Buktikandenganinduksimatematikbahwajika adanorangtamumakajumlahjabattangan yang terjadi adalah n(n 1)/2. 28 4. Perlihatkan bahwa [(p1 p2) . (p2 p3) . . (pn1 pn)][(p1.p2..pn1)pn ]adalah tautologi bilamana p1, p2, , pnadalah proposisi. 29 30 PRINSIP SARANG MERPATI Jika(k+1)ataulebihobyekditempatkankedalamkkotak, makaterdapatpalingsedikitsatukotakyangmemuatdua atau lebih obyek tersebut. Contoh1:Jikaterdapat11pemaindalamsebuahtim sepakbola yang menang dengan angka 12-0, maka haruslah terdapat paling sedikit satu pemain dalam tim yang membuat gol paling sedikit dua kali. Contoh 2: Jika anda menghadiri 6 kuliah dalam selang waktu SeninsampaiJumat,makaharuslahterdapatpalingsedikit satu hari ketika anda menghadiri paling sedikit dua kelas. 31 SOAL Tunjukkanbahwauntuksetiapbilangan bulat n terdapat kelipatan dari n yang hanya terdiri dari digit 0 atau 1 saja. GENERALISASI PRINSIP SARANG MERPATI Jika N obyek ditempatkan ke dalam k kotak, maka terdapat palingsedikitsatukotakyangmemuatsedikitnyaN/k( obyek. Bukti? Contoh1:Didalamkelasdengan60mahasiswa,terdapat palingsedikit12mahasiswaakanmendapatnilaiyang sama (A, B, C, D, atau E). Contoh2:Didalamkelasdengan61mahasiswa,paling sedikit13mahasiswaakanmemperolehnilaiyang sama. 32 1. Berapajumlahminimummahasiswadi dalamkelasMatematikaDiskritagar sedikitnya 6 orang memperoleh nilai yang sama? 2. Berapajumlahminimumkodeareayang dibutuhkanagar25jutanomortelepon mempunyai10-digitnomorteleponyang berbeda? 33 SOAL CONTOH Misalkanadalaciyangberisiselusinkauskakicoklatdan selusinkauskakihitamyangdidistribusikansecaraacak. Pada saat listrik padam, berapa kaus kaki yang harus anda ambiluntukmemastikanbahwadiantaranyaterdapat sepasang kaus yang sewarna? Solusi: Terdapatduatipekauskaki,jadijikaandamemilihpaling sedikit3kauskaki,haruslahterdapatpalingsedikitdua kaus kaki coklat atau paling sedikit dua kaus kaki hitam . Generalisasi Prinsip Sarang Merpati : 3/2( = 2. 34 BEBERAPA APLIKASI 1. Tunjukkanbahwadiantaran+1bilanganbulat positifyangtidakmelebihi2n,haruslah terdapatsuatubilanganbulatyangmembagi salah satu integer lainnya. 2. Tunjukkanbahwasetiapbarisandarin2+1 bilanganrealyangberbedaselalumemuat suatusubbarisandenganpanjangn+1yang monoton naik/monoton turun. 35 TEORI RAMSEY Asumsikan bahwa di dalam suatu kelompok yangterdiridari6orang,setiappasang terdiri dari dua sahabat atau dua musuh. Tunjukkanbahwaterdapattigaorangyang salingbersahabatatautigaorangyang salingbermusuhandalamkelompok tersebut. 36 TEORI RAMSEY (2) BilanganRamseyR(m,n),denganmdann bilanganbulatpositif>2,adalahjumlah minimumorangdalamsuatupesta sehinggaterdapatmorangyangsaling bersahabatataunorangyangsaling bermusuhan,denganmengasumsikan setiappasangorangdipestatersebut adalah sahabat atau musuh. 37