.webp)
Soal induksi matematika berisi tentang rumus atau teknik pembuktian dalam matematika. Teknik induksi matematika diperkenalkan oleh De Morgan pada abad ke-19.
Dikutip dari buku 'Matematika Diskrit' karya Gede Suweken, induksi matematika memiliki dua prinsip yakni prinsip induksi lemah dan prinsip induksi kuat.
Soal Induksi Matematika
SCROLL TO CONTINUE WITH CONTENT
- 1) Prinsip Induksi Matematika (Lemah)
Prinsip ini dinyatakan dengan P(n) adalah suatu pernyataan tentang suatu bilangan asli n, dan q adalah suatu bilangan asli yang tertentu (fixed).
Maka bukti induktif bahwa P(n) adalah benar untuk semua n ≥ q dilakukan melalui 2 (dua) langkah berikut:
a. Langkah awal: Tunjukkan bahwa P(q) adalah benar.
b. Langkah induksi: Tunjukkan bahwa untuk k 2 q bilangan asli, jika P(k) benar, maka P(k+1) juga benar.
Dari dua langkah di atas, maka terbukti bahwa P(n) benar untuk semua bilangan asli n ≥ q. Induksi matematika versi ini dikatakan lemah, karena pada langkah induksinya mengasumsikan P(n) benar untuk satu n saja.
Lemah di sini tidak berarti bahwa bukti yang ditampilkan kurang akurat.
Contoh soal induksi matematika (lemah)
Perhatikan contoh soal induksi matematika berikut ini.
Tunjukkan bahwa 1+2+3+...+n=½n(n+1) untuk semua n bilangan asli.
Pembahasan:
Misalkan P(n) adalah pernyataan bahwa 1+ 2+ 3+ ... + n/2 n(n+1). Tujuan kita adalah menunjukkan bahwa pernyataan P(n) tersebut benar untuk semua n bilangan asli.
Langkah awal: Kita harus menunjukkan bahwa P(1) benar. Dalam hal ini P(1) adalah pernyataan yang bunyinya 1=1(1+1), yang tentu saja benar. Jadi P(1) benar.
Langkah Induksi: Kita harus menunjukkan bahwa jika P(k) benar, P(k+1) juga benar.
Dalam hal ini jika, 1 + 2 + 3 + ... + k = 1/2 k(k+1) apakah 1 + 2 + 3 +...+ k + (k+ 1) = ½ (k+ 1) (k+1+1)= ½ (k+1)(k+2)?
Tentu saja 1+2+3+...+k+ (k+1)= ½ k(k+1) + (k+1) = (k+1)[2k + 1] = (k+1) (k+2) = ½ (k+1) (k+2).
Jadi jika P(k) benar, ternyata P(k+1) juga benar. Dengan dua bukti tersebut maka P(n), pernyataan bahwa 1+2+3+...+ n = ½ n(n+1) adalah benar untuk semua n bilangan asli.
2) Prinsip Induksi Matematika (Kuat)
Dalam hal ini, proses induksi tidak cukup hanya menunjukkan bahwa jika pernyataan P benar untuk satu kasus k ≥ q tapi juga benar untuk pernyataan k+1, yaitu pernyataan P(k+1).
Dalam hal tersebut harus ditunjukkan bahwa P benar untuk semua kasus P(q+1), P(q+2), P(q+3),..., P(k).
Jadi proses pembuktian Induksi Matematika secara kuat (strong mathematical induction) bahwa P(n) benar untuk semua n ≥ q adalah sebagai berikut:
a. Langkah awal: Tunjukkan bahwa P(q) benar
b. Langkah induktif: Tunjukkan bahwa untuk k 2 q, jika P(q+1), P(q+2), P(q+3), ..., dan P(k) benar, maka P(k+1) juga benar.
Proses pembuktian ini adalah kuat dalam artian bahwa dalam langkah pembuktian induktifnya. Kita memiliki lebih banyak informasi dibandingkan dengan pembuktian yang sifatnya lemah.
Contoh soal induksi matematika (kuat)
Tunjukkan bahwa setiap bilangan asli lebih dari 1 dapat dinyatakan sebagai hasil kali atas faktor-faktor primanya.
Pembahasan:
Misalkan P adalah pernyataan bahwa setiap bilangan asli lebih dari 1 dapat dinyatakan sebagai hasil kali atas faktor-faktor primanya. Tentu saja P(2) benar.
Andaikan P(3), P(4), P(5), ..., P(k) benar. Bagaimana menunjukkan bahwa P(k+1) juga benar?
Jika (k+1) adalah bilangan prima, maka P(k+1) benar. Jika (k+1) bukan bilangan prima, maka k+1 = mn, dengan m dan n bilangan-bilangan asli kurang dari k.
Dengan pengandaian sebelumnya maka, m dan n tentu saja bisa dinyatakan sebagai produk dari bilangan-bilangan prima. Sebagai akibatnya, (k+1) juga merupakan hasil kali dari bilangan-bilangan prima.
Itulah contoh soal induksi matematika lengkap dengan pembahasannya. Selamat belajar detikers!
(pay/pay)
