PENGENALAN INDUKSI MATEMATIKA

Mei 20th, 2018

Post kali ini akan memperkenalkan prinsip induksi matematika dan memberikan contoh bagaimana induksi matematika diterapkan untuk membuktikan kebenaran pernyataan-pernyataan yang berkenaan dengan bilangan asli.

 

Perhatikan hal-hal berikut ini:

 

1 + 2 + 3 = 6 dan {3.(3+1)}/2 ~=~ {3.4}/2 ~=~ 6

1 + 2 + 3 + 4 = 10 dan {4.(4+1)}/2 ~=~ {4.5}/2 ~=~ 10

1 + 2 + 3 + 4 + 5 = 15 dan {5.(5+1)}/2 ~=~ {5.6}/2 ~=~ 15

Dari pola tersebut kita dapat menduga:

1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ n ~=~ {n(n+1)}/2  …………………………………………. (*)

 

Yang menjadi pertanyaan sekarang adalah apakah (*) benar untuk setiap bilangan asli n? Di sinilah induksi matematika dapat membantu kita.

 

Prinsip induksi matematika merupakan salah satu dari lima buah postulat Peano (Peano postulates). Misalkan ℕ adalah himpunan yang semua anggotanya (nanti) dinamakan bilangan asli. Berikut ini merupakan postulat-postulat Peano.

Postulat 1

1 ∊ ℕ; artinya ℕ merupakan himpunan tidak kosong yang memuat suatu anggota yang dinyatakan dengan 1.

Postulat 2

Untuk setiap n ∊ ℕ terdapat anggota tunggal n* ∊ ℕ yang dinamakan pelanjut (successor) dari n.

Postulat 3

Untuk setiap n ∊ ℕ, n* ≠ 1; artinya, 1 bukan merupakan pelanjut dari anggota mana pun dalam ℕ.

Postulat 4

Untuk setiap pasangan m, n ∊ ℕ dengan m ≠ n berlaku m* ≠ n*; artinya anggota-anggota ℕ yang berbeda memiliki pelanjut yang berbeda pula.

Postulat 5

Jika (a) A ⊆ ℕ, (b) 1 ∊ A, dan (c) p ∊ A ⇒ p* ∊ A maka A = ℕ.

 

Dengan menerapkan Postulat 1 hingga 4 kita dapat memberikan nama 1* = 2 (pelanjut dari 1 dinamakan 2), 2* = 3 (pelanjut dari 2 dinamakan 3), 3* = 4 (pelanjut dari 3 dinamakan 4), 4* = 5 (pelanjut dari 4 dinamakan 5), dan seterusnya, himpunan yang akan terbentuk adalah A = {1, 2, 3, 4, 5, …} yang anggota-anggotanya berbeda satu sama lain dan A = ℕ menurut Postulat 5.

 

Postulat 5 inilah yang dinamakan prinsip induksi matematika. Prinsip ini sering muncul dalam bentuk seperti berikut ini:

 

Jika untuk setiap bilangan asli n, S(n) merupakan pernyataan yang tergantung pada n maka untuk membuktikan bahwa S(n) merupakan pernyataan yang benar untuk masing-masing dan setiap bilangan asli n, kita definisikan himpunan A sebagai himpunan semua bilangan asli n sedemikian hingga S(n) benar (A ⊆ ℕ). Jika kita dapat membuktikan bahwa S(1) benar (1 ∊ A) dan implikasi S(p) benar mengakibatkan S(p*) benar maka S(n) benar untuk setiap bilangan asli n (A = ℕ). [Catatan: pernyataan “S(p) benar” pada prinsip tersebut dinamakan “hipotesis induksi”]

 

Dengan mendefinisikan operasi penjumlahan dalam ℕ  sebagai p + 1 = p* untuk setiap p ∊ ℕ, prinsip induksi tersebut dapat dinyatakan sebagai berikut.

Jika untuk setiap bilangan asli n, S(n) merupakan pernyataan yang tergantung pada n maka untuk membuktikan bahwa S(n) merupakan pernyataan yang benar untuk masing-masing dan setiap bilangan asli n, kita definisikan himpunan A sebagai himpunan semua bilangan asli n sedemikian hingga S(n) benar (A ⊆ ℕ). Jika kita dapat membuktikan bahwa S(1) benar (1 ∊ A) dan implikasi S(p) benar mengakibatkan S(p+1) benar maka S(n) benar untuk setiap bilangan asli n (A = ℕ).

 

Jadi, untuk membuktikan bahwa suatu pernyataan S(n) yang mengenai bilangan asli n berlaku untuk setiap bilangan asli n, ada dua hal yang harus dibuktikan, yaitu (1) S(1) benar, dan (2) Jika S(p)  benar maka S(p+1) benar.

 

Sekarang mari kita lihat contoh-contoh bagaimana prinsip induksi matematika digunakan untuk membuktikan kebenaran pernyataan yang berkenaan dengan bilangan asli.

 

Contoh 1

Buktikan bahwa 1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ n ~=~ {n(n+1)}/2 benar untuk setiap bilangan asli n.

 

Jawab:

Dalam hal ini, S(n) : 1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ n ~=~ {n(n+1)}/2

Tahap 1: membuktikan S(1) benar.

Substitusikan n = 1 ke dalam S(n).

S(1) : 1 ~=~ {1.(1+1)}/2 (BENAR)

Tahap 2: membuktikan kebenaran implikasi S(p) benar ⇒ S(p+1) benar

Untuk membuktikan implikasi ini, kita misalkan bahwa S(p) benar, yaitu:

1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ p ~=~ {p(p+1)}/2

Yang harus dibuktikan selanjutnya adalah S(p+1) benar, yaitu:

1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ p ~+~ (p+1) ~=~ {(p+1)((p+1)+1)}/2

Karena 1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ p ~=~ {p(p+1)}/2,

1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ p ~+~ (p+1) ~=~ {p(p+1)}/2 ~+~ (p+1)

1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ p ~+~ (p+1) ~= ~ {p(p+1)}/2 ~+~ {2(p+1)}/2

1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ p ~+~ (p+1) ~= ~ {p+1}/2 ~ (p ~+~ 2)

1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ p ~+~ (p+1) ~= ~ {(p+1)(p+2)}/2

1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ p ~+~ (p+1) ~= {(p+1)((p+1)+1)}/2 (terbukti)

Jadi, 1 ~+~ 2 ~+~ 3 ~+~ ... ~+~ n ~=~ {n(n+1)}/2 benar untuk setiap bilangan asli n.

 

Contoh 2

Buktikan bahwa untuk setiap bilangan asli n berlaku 2n ≤ (n+1)!

 

Jawab:

Dalam hal ini, S(n) : 2n ≤ (n+1)!

Tahap 1: membuktikan S(1) benar.

Substitusikan n = 1 ke dalam S(n).

21 ≤ (1+1)! = 2!

2 ≤ 2! (BENAR)

Tahap 2: membuktikan kebenaran implikasi S(p) benar ⇒ S(p+1) benar

Untuk membuktikan implikasi ini, kita misalkan bahwa S(p) benar, yaitu 2p ≤ (p+1)!

Yang harus dibuktikan selanjutnya adalah S(p+1) benar, yaitu 2p+1 ≤ ((p+1)+1)!

Perhatikan bahwa 2p+1 = 2.2p

Karena 2p ≤ (p+1)! dan 2 ≤ p + 2,

2p+1 ≤ (p+2).(p+1)! = (p+2)! = ((p+1)+1)!

2p+1 ≤ ((p+1)+1)! (terbukti)

Jadi, 2n ≤ (n+1)! benar untuk setiap bilangan asli n.

 

Latihan_Induksi_Matematika

 



Most visitors also read :



Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *