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.
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 [pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ n ~=~ {n(n+1)}/2[/pmath] benar untuk setiap bilangan asli n.
Jawab:
Dalam hal ini, S(n) : [pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ n ~=~ {n(n+1)}/2[/pmath]
Tahap 1: membuktikan S(1) benar.
Substitusikan n = 1 ke dalam S(n).
S(1) : [pmath]1 ~=~ {1.(1+1)}/2[/pmath] (BENAR)
Tahap 2: membuktikan kebenaran implikasi S(p) benar ⇒ S(p+1) benar
Untuk membuktikan implikasi ini, kita misalkan bahwa S(p) benar, yaitu:
PENGENALAN INDUKSI MATEMATIKA
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 [pmath]{3.(3+1)}/2 ~=~ {3.4}/2 ~=~ 6[/pmath]
1 + 2 + 3 + 4 = 10 dan [pmath]{4.(4+1)}/2 ~=~ {4.5}/2 ~=~ 10[/pmath]
1 + 2 + 3 + 4 + 5 = 15 dan [pmath]{5.(5+1)}/2 ~=~ {5.6}/2 ~=~ 15[/pmath]
Dari pola tersebut kita dapat menduga:
[pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ n ~=~ {n(n+1)}/2[/pmath] …………………………………………. (*)
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 [pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ n ~=~ {n(n+1)}/2[/pmath] benar untuk setiap bilangan asli n.
Jawab:
Dalam hal ini, S(n) : [pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ n ~=~ {n(n+1)}/2[/pmath]
Tahap 1: membuktikan S(1) benar.
Substitusikan n = 1 ke dalam S(n).
S(1) : [pmath]1 ~=~ {1.(1+1)}/2[/pmath] (BENAR)
Tahap 2: membuktikan kebenaran implikasi S(p) benar ⇒ S(p+1) benar
Untuk membuktikan implikasi ini, kita misalkan bahwa S(p) benar, yaitu:
[pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ p ~=~ {p(p+1)}/2[/pmath]
Yang harus dibuktikan selanjutnya adalah S(p+1) benar, yaitu:
[pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ p ~+~ (p+1) ~=~ {(p+1)((p+1)+1)}/2[/pmath]
Karena [pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ p ~=~ {p(p+1)}/2[/pmath],
[pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ p ~+~ (p+1) ~=~ {p(p+1)}/2 ~+~ (p+1)[/pmath]
[pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ p ~+~ (p+1) ~= ~ {p(p+1)}/2 ~+~ {2(p+1)}/2[/pmath]
[pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ p ~+~ (p+1) ~= ~ {p+1}/2 ~ (p ~+~ 2)[/pmath]
[pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ p ~+~ (p+1) ~= ~ {(p+1)(p+2)}/2[/pmath]
[pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ p ~+~ (p+1) ~= {(p+1)((p+1)+1)}/2[/pmath] (terbukti)
Jadi, [pmath]1 ~+~ 2 ~+~ 3 ~+~ … ~+~ n ~=~ {n(n+1)}/2[/pmath] 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
Bagikan ini:
Most visitors also read :
BERKENALAN DENGAN NILAI DAN VEKTOR EIGEN
DEKOMPOSISI NILAI SINGULAR (SINGULAR VALUE DECOMPOSITION)
MATRIKS AKAR KUADRAT
SOAL DAN PEMBAHASAN ANALISIS KOMPONEN UTAMA