Belajar Dasar Induksi Matematika
Penulis: Lintang ErlanggaMateri satu ini benar-benar unik, dan patut dipelajari. Karena kebenaran sebuah pernyataan yang mewakili banyak hal dapat dibuktikan tapi hanya dengan menguji beberapa kondisi saja.
Supaya lebih jelasnya, gas! Langsung baca aja.
Daftar Isi
Pembuktian Dalam Matematika
Suatu pernyataan dalam matematika tentu perlu ada hal yang mendasarinya, apakah pernyataan tersebut benar atau salah.
Salah satu cara untuk membuktikan kebenaran pada suatu pernyataan yakni menggunakan induksi matematika.
Teknik ini merupakan salah satu cara dari sekian banyaknya metode untuk membuktikan suatu pernyataan matematika.
Di antaranya yaitu:
- Pembuktian langsung (direct proof): Secara eksplisit sebuah pernyataan dibuktikan kebenarannya.
- Pembuktian secara kontradiksi (contradiction proof): Pernyataan dibuktikan dengan menganggap saat kesimpulannya salah, maka harus bertolak belakang dengan aslinya.
- Pembuktian secara kontraposisi (contraposition proof): Kesimpulan dari sebuah pernyataan dianggap salah atau tidak pernah terjadi, maka begitupun penyebabnya.
Pada induksi matematika, suatu pernyataan diperiksa apakah kebenarannya berlaku untuk semua bilangan bulat positif.
Pernyataan tersebut bisa apa aja, dapat berupa sebuah persamaan yang mewakili jumlahan deret bilangan, bisa juga berupa fungsi yang hasil pemetaaannya selalu habis dibagi suatu bilangan. Banyak macem deh pokoknya.
Maksud dari kalimat sebelumnya adalah, jika suatu preposisi (pernyataan yang hanya bisa salah atau benar saja, tidak bisa keduanya) mengatakan bahwa jumlah semua n buah bilangan positif pertama, besarnya diwakili oleh rumus:
Dengan demikian, preposisi tersebut harus berlaku ketika n = 0, 1, 2, 3, ..., dan seterusnya.
Maksudnya, ketika n = 5 jumlahnya harus sesuai dengan 0 + 1 + … + 5. Begitu juga saat n = 10, berikut yang lainnya.
Sangat mustahil bagi kita untuk memeriksanya satu per satu, mengingat jumlah bilangan bulat positif sendiri begitu banyak.
Mungkin bisa menjadi motivasi tersendiri, mengapa muncul induksi matematika di dunia ini.
Induksi Matematika
Prinsip induksi matematika itu cukup sederhana, kita perlu membuktikan bahwa, jika pada suatu indeks ke k benar, maka akan menyebabkan indeks ke k + 1 juga benar.
Ini adalah bentuk implikasi, jika P maka Q atau secara simbol matematisnya:
Angga aja telah membuat suatu implikasi yang sifatnya beranjak naik, dari indeks terkecil dan seterusnya. Maka dari itu, perlu dicari kebenaran dari indeks terkecil alias pertama.
Masih belum ada bayangan bagaimana pembuktiannya bekerja? Coba bayangkan, misal untuk indeks pertama kita sudah membuktikan kebenarannya.
Karena kita telah memeriksa bahwa pada sembarang indeks, kayak tadi pada k serta k + 1 kebenarannya sudah terbukti.
Nah, dengan adanya implikasi sebelumnya maka secara gak langsung kita juga udah membuktikan bahwa pernyataan setelah indeks pertama dan selanjutnya juga benar.
Maka ilustrasinya sebagai berikut. Telah dibuktikan secara tersendiri P(1) benar maka P(2) benar, karena P(2) benar, maka P(3) benar, dan begitu seterusnya.
Oleh karena itu, teknik induksi matematika ini sering diilustrasikan dengan apa yang disebut dominos effect.
Satu jatuh maka semua jatuh, kalau dalam bahasan kali ini, analoginya satu benar maka semuanya benar.
Apabila dirangkum, demikian proses secara umumnya yakni sebagai berikut:
- Buktikan bahwa untuk n yang pertama, preposisi terpenuhi.
- Asumsikan indeks sembarang n pada k, P(k).
- Jika P(k) benar maka indeks selanjutnya yaitu pada k + 1, maka P(k + 1) harus juga benar.
Contoh Pembuktian
Biar dapat gambaran lebih, sekarang coba kita selesaikan contoh berikut ini.
Kita akan coba membuktikan bahwa 52n + 1 + 22n + 1 habis dibagi oleh 7 untuk n ≥ 0.
Periksa Indeks Terkecil
Biar lebih sederhana, kita langsung gunakan rangkuman proses sebelumnya aja.
Pertama periksa apakah untuk n pertama habis dibagi 7, yang mana dalam kasus ini adalah n = 0.
Untuk n = 0, rumus tersebut menghasilkan nilai 7, 52(0) + 1 + 22(0) + 1 = 7. Sangat terlihat jelas bahwa, 7 sudah tentu habis dibagi dengan 7, dengan demikian terbukti dan langkah satu selesai.
Langkah Induktif
Untuk membuktikan implikasinya, asumsikan pada suatu indeks sebut saja n = k berlaku rumus sebelumnya, yakni 52n + 1 + 22n + 1 harus habis dibagi 7.
Untuk itu, pada indeks berikutnya yaitu pada n = k + 1 harus habis dibagi 7 juga.
Kemudian kita urai ekspresi di atas, berarti ada 52 = 25 buah suku 52k + 1 dan terdapat 22 = 4 buah suku 22k + 1, atau bisa kita tuliskan menjadi:
Lalu disusun ulang menjadi:
Perlu diperhatikan bahwa 4(52k + 1 + 22k + 1) jelas habis dibagi 7 karena memuat asumsi yang telah kita buat di awal, sedangkan 21(52k + 1) karena ada konstanta 21 yang merupakan kelipatan 7, akibatnya habis juga dibagi 7.
Dengan demikian karena kedua suku di atas habis dibagi 7, yang menyebabkan pada indeks n = k + 1 otomatis habis dibagi 7, sehingga terbuktilah preposisi di atas.
Berdasarkan solusi ini, di sini terlihat jelas bahwa bentuk implikasi dan pembuktian untuk indeks paling awal saling berkaitan. Maksudnya, keduanya harus terpenuhi apabila ingin membuktikan kebenarannya, tidak boleh salah satunya saja.
Contoh Pembuktian Lainnya
Contoh lainnya, anggap kita mau membuktikan rumus dari jumlahan suatu deret bilangan.
Cek Indeks Pertama
Buktikan terlebih dahulu untuk indeks paling pertama yaitu n = 0.
Dengan begitu, maka rumus tersebut berlaku atau terbukti untuk n = 0.
Periksa Implikasinya
Kemudian dilanjutkan dengan memeriksa bentuk implikasinya. Asumsikan untuk indeks sembarang berada di k, maka untuk indeks selanjutnya yaitu di k + 1 juga harus berlaku.
Anggap pada indeks ke k benar, sehingga:
Untuk membuktikan bahwa pada k + 1 juga benar, maka harus kita perlihatkan bahwa jumlahan pada ke k + 1 harus sama dengan jumlahan ke k ditambah (k + 1)2. Yaitu nilainya sama seperti:
Langsung kita cari saja jumlahannya dengan mensubsitusikan k + 1.
Terbukti sudah kebenaran dari rumus untuk mencari jumlahan ini. Dan kita tidak perlu repot-repot mengeceknya satu-satu.
Tidak ada batasan, mana yang ingin kalian buktikan terlebih dahulu. Implikasinya atau pada indeks awalnya terlebih dahulu, silahkan dipilih mana yang menurut kalian lebih masuk akal.
Namun memang yang paling sederhana biasanya yaitu membuktikan indeks awalnya terlebih dahulu.
Membuktikan bentuk implikasinya terlebih dahulu biasanya memang repot, karena memerlukan banyak manipulasi bentuk matematikanya.
Makanya umumnya orang memprioritaskan membuktikan kebenaran pada indeks pertama.