Dalam kehidupan sehari-hari, kita seringkali terlibat dalam membuat keputusan: apakah keputusan tersebut sesuai dengan kebutuhan, bagaimana menghasilkan keputusan yang terbaik, dan seterusnya. Keputusan tersebut di antaranya memerlukan kemampuan logika yang benar, termasuk dalam matematika. Sebagaimana dalam kehidupan sehari-hari, ketika mempelajari matematika pun kita perlu melibatkan cara berpikir yang benar. Artinya, untuk memahami sesuatu kita mesti memahami konsepnya.
Karena itulah, matematika bukan sekadar kumpulan rumus yang hanya dihafalkan untuk bisa menyelesaikan soal dengan cepat. kumpulan rumus itu mesti memiliki ‘strong why‘ di baliknya: kenapa rumusnya bisa begitu, darimana rumus itu berasal. Nah, pembahasan yang seperti itu di matematika kita mengenal adanya induksi matematika.
Konsep Dasar
Misalkan kita letakkan domino-domino yang berderet panjang sekali. Saat kita menjatuhkan domino pertama ke arah domino kedua, domino ketiga keempat kelima dan seterusnya juga akan ikut jatuh. Yap, prinsip dasar dari induksi matematika ini sederhana: efek domino. Dalam konteks induksi matematika, ketika kita hendak menguji atau membuktikan suatu rumus, kita harus pastikan bahwa rumus itu benar untuk semua bilangan, dalam hal ini, bilangan asli.
Misalkan ada satu deret bilangan asli 1, 2, 3, 4, 5, …, n. Jumlah deret bilangan (Sn) untuk n = 3 adalah 1+2+3 = 6. Kalau n = 4, S4 = 1+2+3+4 = 10. Jika n = 5, S5 = 15. Dari pola tersebut, kalau kita jumlahkan semua bilangan tersebut dari 1 sampai dengan n, kita akan dapatkan rumusnya sebagai berikut.
Nah, masalahnya, rumus di atas berlaku universal, nggak? Berlaku semua kasus atau hanya pada kasus tertentu saja?
Pembuktian
Untuk membuktikan bahwa rumus di atas, kita pakai prinsip efek domino. Kalau domino pertama jatuh, domino kedua harus jatuh, domino ketiga juga harus jatuh. Begitupun domino keempat, dan seterusnya. Dari prinsip tersebut, kita dapat membahasakannya secara matematis lewat dua langkah sebagai berikut.
Basic step: untuk n = 1, rumus S1 adalah benar.
Inductive Step: jika rumus tersebut benar untuk n = k, maka rumus tersebut juga benar untuk n = k+1, dengan .
Bagaimana kita menerapkan dua langkah di atas untuk membuktikan suatu rumus? Coba kita balik lagi ke rumus jumlah deret bilangan sebelumnya. Dengan mengacu pada efek domino secara matematis, kita masukkan n = 1 ke rumus Sn. Hasilnya adalah sebagai berikut.
Berarti untuk n = 1, rumus di atas benar. Selanjutnya kita uji dengan memasukkan n = k ke dalam rumus Sn, jadinya seperti di bawah ini.
Oke. Menurut inductive step kalau rumus itu benar untuk n = k, maka ia juga harus benar untuk n = k+1. Sekarang kita masukkan n = k +1 ke dalam rumus tersebut.
Nah, coba kita perhatikan. Ternyata ia berasal dari jumlah deret kayak di bawah.
Sk = 1 + 2 + 3 + . . . + k
Sk+1 = 1 + 2 + 3 + . . . + k + (k + 1)
Sekarang kita bisa kelompokkan ulang Sk+1 menjadi seperti berikut.
Sk+1 = [1 + 2 + 3 + . . . + k] + (k + 1)
[1 + 2 + 3 + . . . + k] itu ‘kan sama dengan Sk, sedangkan Sk = (k(k+1))/2. Coba kita masukkan nilai Sk ke dalam Sk+1 yang deretnya sudah dikelompokkan ulang.
Sk+1 = Sk + (k + 1)
Jadi, rumus penjumlahan deret Sn di atas benar untuk n = k+1.
Perlu diketahui bahwa basic step merupakan bagian mendasar dalam pembuktian induksi. Tanpa basic step, pembuktian dengan cara induksi tidak akan sempurna. Pernyataan inductive step berfungsi untuk memastikan bahwa bilangan asli apapun, setelah n = 1, bisa berlaku untuk rumus atau pernyataan matematis yang hendak kita buktikan. Terlebih lagi kita ingin memastikan bahwa suatu rumus atau pernyataan matematis itu berlaku universal.
Terus, untuk inductive step, bagaimana kita bisa tahu untuk suatu rumus P(n) dengan n = k, rumus itu juga berlaku untuk n = k + 1? Di pembuktian inductive step, kita memunculkan Sk+1 yang sama dengan Sk ditambah dengan (k + 1), Sk+1 = Sk + (k + 1). Berangkat dari pernyataan matematis tersebut, kita telah membuktikan bahwa Sn itu benar untuk n = k + 1.
Contoh Soal
1. Gunakan induksi matematika untuk membuktikan persamaan jumlah deret P(i) = 1 + 22 + 32 + 42 + . . . + i2 sebagaimana di bawah, untuk setiap bilangan asli.
Kita mulai dengan basic step: P(i) itu berlaku untuk n = 1, sehingga
Berikutnya, asumsikan bahwa n = k. Maka,
Kita juga ingin membuktikan bahwa P(n) juga berlaku untuk n = k + 1, sehingga
yang itu dapat dibuktikan dengan menambahkan (k + 1) pada P(k) = 1 + 22 + 32 + 42 + . . . + k2 , sehingga menjadi
Oleh karena itu, persamaan jumlah deret P(i) juga berlaku untuk n = k + 1, sehingga memenuhi aturan induksi matematika.
2. Satu lagi contoh soal menarik. Untuk setiap bilangan asli n, coba kita buktikan bahwa 4 membagi 5n – 1.
Pernyataan matematis di atas bisa kita nyatakan ulang sebagai berikut.
dengan P(n) merupakan hasil bagi 5n – 1 dengan 4 dalam bentuk fungsi.
Seperti biasa, kita uji persamaan di atas dengan membuktikan bahwa P(n) berlaku untuk n = 1, sehingga
Selanjutnya, kita uji bahwa jika P(n) berlaku untuk n = k, maka ia juga berlaku untuk n = k + 1. Artinya, jika P(k) adalah benar, maka P(k+1) juga benar; sehingga “4 membagi 5n – 1” adalah benar. Jadi, kita asumsikan k adalah benar, sehingga P(k) adalah benar.
Asumsikan bahwa seiring naiknya nilai k, ada bilangan bulat m sedemikian rupa sehingga
Setelah mengasumsikan P(k) benar, kita coba buktikan bahwa P(k+1) juga benar.
Karena 5k = 4m + 1, maka
Karena 5m + 1 ialah bilangan bulat, maka 4 membagi 5k+1 – 1 adalah benar.
Referensi
Kwong, Harris. (2015). A Spiral Workbook for Discrete Mathematics. California: LibreTexts.
Sundstrom, Ted. (2021). Mathematical Reasoning – Writing and Proof. California: LibreTexts.