Contoh Soal Induksi Matematika Lengkap dengan Pembahasannya

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

• 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!