CHAPTER 5
INDUCTION AND RECURSION
5.1 MATHEMATICAL INDUCTION
Jumlah n Bilangan Ganjil Positif 1=1 1+3=4 1+3+5=9 1 + 3 + 5 + 7 = 16 1 + 3 + 5 + 7 + 9 = 25 Tebakan: “Jumlah dari n bilangan ganjil positif pertama adalah n2.”
Metoda apa yang dapat dipakai untuk membuktikan bahwa tebakan ini benar?
Logika dan Induksi Modus ponens p p→q q Double modus ponens p0 p0 → p 1 p1 → p 2 p2 Dapat diperoleh triple modus ponens, quadruple modus ponens, dst. Sehingga kita dapat melakukan penarikan kesimpulan untuk bilangan bulat sebarang.
Domino dan Induksi Aksioma induksi untuk bilangan bulat dapat dilihat sebagai THE GREAT LEAP TO INFINITY
Diberikan barisan tak hingga domino yang terhitung. Misalkan: (1) Domino pertama jatuh. (2) Jika domino n jatuh, demikian juga domino n + 1. Kesimpulan: Semua domino akan jatuh.
Domino dan Induksi (2)
Induksi Matematika • Merupakan teknik pembuktian yang sangat penting • Dipergunakan secara luas untuk membuktikan pernyataan yang berkaitan dengan objek diskrit. (kompleksitas algoritma, teorema mengenai graf, identitas dan ketidaksamaan yang melibatkan bilangan bulat, dsb). • Tidak dapat digunakan untuk menemukan rumus atau teorema, tetapi hanya untuk melakukan pembuktian.
Prinsip Induksi Matematika Teknik untuk membuktikan kebenaran proposisi P(n) untuk setiap n bilangan bulat positif. Suatu bukti dengan menggunakan induksi matematika bahwa “P(n) benar untuk setiap n bilangan bulat positif “ terdiri dari tiga langkah: 1. Langkah basis: Tunjukkan bahwa P(1) benar. 2. Langkah induktif: Tunjukkan bahwa P(k) P(k + 1) benar untuk setiap k. P(k) untuk suatu k tertentu disebut hipotesa induksi. 3. Konklusi: n P(n) bernilai benar.
Sifat Terurut dengan Baik Validitas dari induksi matematika dapat diturunkan dari suatu aksioma fundamental tentang himpunan bilangan bulat. Sifat Terurut dengan Baik (Well-Ordering Property) Setiap himpunan bilangan bulat positif yang tak kosong selalu memiliki anggota terkecil.
Mengapa Induksi Matematika Suatu Teknik Pembuktian yang Valid? Misalkan kita tahu bahwa P(1) benar dan P(k) P(k + 1) k. Bagaimana menunjukkan bahwa P(n) benar n? Dengan menggunakan kontradiksi. Andaikan ada bilangan bulat sehingga P(n) salah. Misalkan S adalah himpunan bilangan bulat n yang mengakibatkan P(n) salah. Dengan demikian S tak kosong dan menurut well-ordering property, S memiliki anggota terkecil, misalkan m. Kita tahu bahwa m bukan 1, karena P(1) benar. Karena m positif dan lebih besar dari 1, m−1 adalah bilangan bulat positif. Karena m−1 < m, maka m-1 bukan anggota S, sehingga P(m-1) benar. Karena pernyataan P(m− 1) →P(m) juga benar, maka haruslah P(m) benar, suatu kontradiksi. Maka, P(n) haruslah benar untuk semua bilangan bulat n.
Contoh 1 Tebakan:
“Jumlah dari n bilangan ganjil positif pertama adalah n2.” Bukti. Misalkan P(n): “Jumlah dari n bilangan ganjil positif pertama adalah n2.” 1. Langkah basis: P(1) benar, karena 1 = 12. 2. Langkah induktif: Asumsikan bahwa P(k) benar untuk semua k, yaitu 1 +3 + 5 + … + (2k-1) = k2. Kita perlu menunjukkan bahwa P(k + 1) benar, yaitu 1 +3 + 5 + … + (2k-1) + (2k+1) = (k+1)2. 1 +3 + 5 + … + (2k-1) + (2k+1) = k2 + (2k+1) = (k+1)2 3. Konklusi: “Jumlah dari n bilangan ganjil positif pertama adalah n2.”
Contoh 2 Tunjukkan bahwa n < 2n untuk setiap bilangan bulat positif n. Solusi. Misalkan P(n): “n < 2n.” 1. Langkah basis: P(1) benar, karena 1 < 21 = 2. 2. Langkah induktif: Asumsikan bahwa P(k) benar untuk semua k, yaitu k < 2k. Kita perlu menunjukkan bahwa P(k + 1) benar, yaitu k + 1 < 2k+1 Kita mulai dari k < 2k k + 1 < 2k + 1 2k + 2k = 2k+1 Jadi, jika k < 2k maka k + 1 < 2k+1 3. Konklusi: Jadi, n < 2n benar untuk setiap n bilangan bulat positif.
Contoh 3 Tunjukkan bahwa jika S adalah himpunan hingga dengan n anggota, maka S mempunyai 2n subhimpunan. Solusi. P(n): proposisi “himpunan hingga dengan n anggota mempunyai 2n subhimpunan”. 1.Langkah basis: P(0) benar, karena himpunan dengan nol anggota, yaitu himpunan kosong, mempunyai tepat 20 = 1 subhimpunan. 2.Langkah induktif: Asumsikan bahwa P(k) benar untuk semua k, yaitu himpunan dengan k anggota mempunyai 2k subhimpunan. Kita perlu menunjukkan bahwa P(k + 1) benar, yaitu himpunan dengan (k+1) anggota mempunyai 2(k+1) subhimpunan.
Contoh 3 (2) Misalkan T: himpunan dengan k+1 anggota. Dapat ditulis T = S {a} dengan aT dan S = T – {a}. a X X
T
S X {a}
a
T
Untuk setiap subhimpunan X dari S, terdapat tepat dua subhimpunan T, yaitu X dan X {a}, yang membentuk semua subhimpunan T dan semuanya berbeda. Jadi, terdapat 2 . 2k = 2(k+1) subhimpunan dari T. 3. Konklusi:
Jadi, setiap himpunan hingga dengan n anggota mempunyai 2n subhimpunan”
Contoh 4 [Gauss] 1 + 2 + … + n = n (n + 1)/2 Bukti. Misalkan P(n): proposisi 1 + 2 + … + n = n (n + 1)/2 1. Langkah basis: Untuk n = 0 diperoleh peroleh 0 = 0. Jadi, P(0) benar. 2. Langkah induktif: Asumsikan bahwa P(k) benar untuk semua k, yaitu 1 + 2 + … + k = k (k + 1)/2 Akan ditunjukkan bahwa P(k + 1) benar, yaitu 1 + 2 + … + k + (k + 1) = (k + 1) ((k + 1) + 1)/2 Dari 1 + 2 + … + k = k (k + 1)/2, diperoleh 1 + 2 + … + k + (k + 1) = k (k + 1)/2 + (k + 1) = (2k + 2 + k (k + 1))/2 = (2k + 2 + k2 + k)/2 = (2 + 3k + k2 )/2 = (k + 1) (k + 2)/2 = (k + 1) ((k + 1) + 1)/2 3. Konklusi: Jadi 1 + 2 + … + n = n (n + 1)/2 benar untuk setiap nN.
Soal 1 [Carmony (1979)] Sejumlah ganjil orang berdiri di suatu lapangan dengan jarak antar dua orang berbeda. Pada waktu yang bersamaan, setiap orang melempar kue pada orang yang terdekat dengan mereka, dan mengenai orang tersebut. Gunakan induksi matematika untuk membuktikan bahwa ada paling sedikit satu orang yang tidak terkena lemparan kue. Catatan. Hal ini tidak berlaku jika terdapat sejumlah genap orang.
Soal 2 Misalkan n suatu bilangan bulat positif. Tunjukkan bahwa setiap papan catur berukuran 2n x 2n yang satu kotaknya dihilangkan dapat selalu ditutupi oleh potongan berbentuk-L.
Pembuktian yang salah dalam Induksi Misalkan P(n) menyatakan bahwa “setiap n garis berbeda pada bidang, tidak ada dua yang sejajar, berpotongan pada satu titik”. Bukti: 1.Langkah basis: P(2) benar karena setiap 2 garis yang tidak sejajar berpotongan pada satu titik. 2.Langkah Induktif: Misalkan P(k) benar. Setiap k garis, tidak ada dua garis yang sejajar, berpotongan pada satu titik.
Pembuktian yang salah dalam Induksi • Ambil sebarang k+1 garis berbeda, tidak ada dua yang sejajar. Misalkan garis-garis tersebut: G1, G2, …, Gk , Gk+1. • HI: G1, G2, …, Gk berpotongan di satu titik t1. • HI: G2, G3 …, Gk+1 berpotongan di satu titik t2. • Bila t1 ≠ t2 maka semua garis yang melalui keduanya akan sama, kontradiksi. • Sehingga t1 = t2. Semua garis melalui t1. • Kesimpulan: P(k+1) benar. Terbukti.
APA YANG SALAH ? • Kesalahan dalam pembuktian tadi agak halus. • Langkah induksi memerlukan bahwa k ≥ 3. • Kita tidak dapat menunjukkan P(2) P(3).
• t1 : titik potong G1 dan G2 . • t2 : titik potong G2 dan G3. • Namun, t1 tidak harus sama t2.
5.2 STRONG INDUCTION
Induksi Kuat (Prinsip Kedua Induksi Matematika) Terdapat bentuk lain dari induksi matematika yang sering dipergunakan dalam bukti. 1. Langkah basis: Tunjukkan bahwa P(0) benar. 2. Langkah induktif: Tunjukkan bahwa jika P(0) dan P(1) dan … dan P(k) benar, maka P(k + 1) untuk setiap kN. 3. Konklusi: n P(n) bernilai benar.
Contoh 5 Tunjukkan bahwa setiap bilangan bulat yang lebih besar dari 1 dapat dituliskan sebagai hasil kali bilangan prima. Solusi. P(n): proposisi “setiap bilangan bulat n yang lebih besar dari 1 dapat dituliskan sebagai hasil kali bilangan prima”. 1. Langkah basis: P(2) benar, karena 2 adalah hasil kali dari satu bilangan prima, dirinya sendiri.
Contoh 5 2. Langkah induktif: • Asumsikan P(j) benar untuk semua bilangan bulat j, 1 < j k. • Harus ditunjukkan bahwa P(k+1) juga benar. Ada dua kasus yang mungkin: – Jika (k + 1) bilangan prima, maka jelas P(k + 1) benar. – Jika (k + 1) bilangan komposit, (k+1) dapat ditulis sebagai perkalian dua buah bilangan bulat a dan b sehingga 2 a b < k + 1. Oleh hipotesa induksi, a dan b keduanya dapat dituliskan sebagai hasil kali bilangan prima. Jadi, k + 1 = a b dapat ditulis sebagai hasil kali bilangan prima.
Contoh 5 3. Konklusi: “Setiap bilangan bulat yang lebih besar dari 1 dapat dituliskan sebagai hasil kali bilangan prima”.
Soal 3 Dalam suatu permainan, dua pemain secara bergantian mengambil sejumlah korek api yang berasal dari salah satu dari dua tumpukan korek api. Pemain yang mengambil korek api terakhir adalah yang menang. Tunjukkan bahwa jika kedua tumpukan korek api memuat korek api dalam jumlah yang sama, pemain kedua selalu dapat menjadi pemenang.
Soal 4 Tunjukkan bahwa setiap biaya pengiriman surat (dalam ribuan) dengan menggunakan perangko seharga Rp12.000 atau lebih dapat dilakukan dengan hanya menggunakan sekumpulan perangko seharga Rp4.000 dan Rp5.000.
