Induksi Matematika

Induksi matematika merupakan suatu metode untuk membuktikan bahwa suatu pernyataan tertentu berlaku untuk setiap bilangan asli. Ada beberapa jenis: induksi matematika sederhana, induksi matematika diperluas, dan induksi matematika kuat.

> Induksi Matematika Sederhana

Induksi Matematika memiliki langkah dasar yang harus ditempuh untuk membuktikan bahwa kebenaran suatu pernyataan berlaku untuk setiap bilangan asli. Adapun langkah-langkahnya adalah sebagai berikut.

1. Langkah dasar: Pada langkah ini, Quipperian harus membuktikan bahwa suatu pernyataan berlaku untuk P(1) atau P(n).
2. Langkah induksi: Jika suatu pernyataan berlaku untuk P(1) atau P(n), maka pernyataan itu juga harus berlaku untuk p(k) atau P(k + 1).

Contoh Soal

Buktikan bahwa penjumlahan n bilangan asli berurutan berlaku!

Pembahasan:

• Pertama-tama, kamu harus menentukan langkah dasarnya.

Langkah dasar:

Oleh karena P(1) = 1, maka jelas benar (berlaku), artinya P(n₀) = benar

• Langkah induksi: Jika P(1) benar, maka pernyataan tersebut harus benar untuk P(k+1) dengan k ≥ n₀,
  
  
  

Benar, Sehingga ;

Oleh karena P(k + 1) mengikuti bentuk pernyataan P(n), maka P(k) bernilai benar.

bernilai benar untuk semua bilangan n ≥ 1.

> Induksi Matematika Diperluas

Setiap pernyataan yang memuat n bilangan asli, ternyata tidak harus dimulai dari angka 1, lho. Itulah sebabnya, Induksi Matematika bisa diperluas dengan langkah-langkah berikut.

1. Langkah dasar: Pembuktian bahwa suatu pernyataan berlaku untuk P(m).
2. Langkah induksi: Pembuktian bahwa jika pernyataan berlaku untuk P(k), dengan k≥m, maka pernyataan tersebut juga berlaku untuk P(k + 1).

Contoh Soal

Buktikan bahwa n²≥ 2n + 7 untuk semua bilangan asli n≥5.

Penyelesaian :

1. Teman-teman  harus memisalkan bahwa P(n) = n²≥ 2n + 7  untuk semua bilangan asli n≥4.

Bilangan asli yang bisa Teman-teman masukkan di awal, bukanlah 1 melainkan 4 karena terdapat keterangan bahwa semua bilangan asli n≥4.

Artinya, P(4) bernilai benar

2. Selanjutnya, Teman-teman harus memisalkan bahwa P(k) benar untuk k≥4 (hipotesis induksi).

Berdasarkan hipotesis di atas diperoleh:

Setelah  mendapatkan persamaan di atas, cobalah buktikan bahwa P(k + 1) juga bernilai benar.

(k+1)²≥ 2(k+1) + 7

Hipotesis induksi menyatakan bahwa (k+1)²≥ 2(k+1) + 14 bernilai benar, maka (k+1)²≥ 2(k+1) + 7 otomatis juga akan bernilai benar karena 14 > 7.

Jadi, pernyataan n²≥ 2n + 7  benar untuk setiap n≥4.

> Induksi Matematika Kuat

Prinsip dasar pada induksi matematika kuat ini berbeda dengan sebelumnya. Jika sebelumnya cukup membuktikan bahwa P(1) benar, maka pada induksi matematika kuat ini, pernyataan harus bernilai benar untuk P(1), P(n_o + 1), P(n_o + 2), …, P(k). Selain itu, Quipperian juga harus membuktikan pernyataan benar untuk P(k + 1). Berikut ini adalah langkah-langkah yang harus Quipperian tempuh untuk induksi matematika kuat.

1. Langkah dasar: Buktikan bahwa P(n_o) benar.
2. Langkah induksi: Jika P(n_o), P(n_o+ 1), P(n_o + 2), …, P(k) benar untuk k ≥ n_o, maka gunakan hal itu untuk membuktikan bahwa P(k + 1) juga benar.

Contoh Soal

Buktikan bahwa setiap bilangan bulat positif n ≥ 2 dapat dinyatakan sebagai perkalian dari satu atau lebih bilangan prima.

Pembahasan:

1. harus menentukan langkah dasarnya terlebih dahulu, yaitu n = 2 dengan 2 merupakan bilangan prima, sehingga pernyataan ini benar.

2.  bisa melanjutkan dengan menentukan langkah induksinya.

Coba  misalkan bahwa 2, 3, 4, 5, …, k dapat dinyatakan sebagai hasil perkalian antara satu atau lebih bilangan prima. Dengan demikian, k +1 juga merupakan hasil perkalian antara satu atau lebih bilangan prima. Artinya  k + 1 bisa berupa bilangan prima atau nonprima (komposit).

• Jika k + 1 merupakan bilangan prima, maka k + 1 dapat dinyatakan sebagai hasil kali k  + 1 itu sendiri.
• Jika k + 1 bukan bilangan prima, maka pembagi k + 1 tidak hanya 1 atau k + 1 itu sendiri, melainkan ada bilangan lain. Misalnya, bilangan lain itu dinotasikan p dan hasil baginya q. Secara matematis, dapat ditulis sebagai berikut.

• Oleh karena 2 ≤ p, q ≤ k, maka nilai p dan q yang mungkin, yaitu 2, 3, 4, …, k. Jika Quipperian perhatikan, nilai p dan q yang mungkin merupakan hasil kali satu atau lebih bilangan prima, sehingga pq jelas menunjukkan hasil kali satu atau lebih bilangan prima. Oleh karena k + 1 = pq, maka k + 1 juga merupakan hasil kali satu atau lebih bilangan prima. Artinya, P(k + 1) bernilai benar.

Jadi, terbukti ya  jika pernyataan n ≥ 2 benar untuk setiap bilangan asli n ≥ 2.