Induksi Matematika
INF-104 Matematika Diskrit Teori Bilangan
[email protected] Jurusan Informatika FMIPA Unsyiah
April 13, 2013
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
Metode pembuktian untuk pernyataan perihal bilangan bulat adalah induksi matematik. Induksi matematik merupakan teknik pembuktian yang baku di dalam matematika. Contoh, misalkan pernyataan terbuka: p(n): ”Jumlah bilangan bulat positif dari 1 sampai n adalah n(n + 1)/2”. Buktikan p(n) benar. Melalui induksi matematik kita dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
Prinsip terurut dengan baik (well-ordering principle) Misalkan Z+ = {x ∈ Z|x > 0} = {x ∈ Z|x ≥ 1}. Setiap subhimpunan tak kosong dari Z+ memuat sebuah elemen terkecil. Kita katakan bahwa Z+ terurut dengan baik. Prinsip induksi matematik ( principle) Misalkan S(n) menyatakan pernyataan matematika terbuka yang melibatkan satu atau lebih variabel n yang mana menyatakan bilangan bulat positif. a) Jika S(1) benar; dan b) Jika bilamana S(k) benar (untuk suatu k tertentu, tetapi pemilihannya sebarang, k ∈ Z+ ),maka S(k + 1) benar; maka S(n) benar untuk semua n ∈ Z+ .
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
1
Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah induksi.
2
Langkah induksi berisi asumsi (andaian) yang menyatakan bahwa p(k) benar. Asumsi tersebut dinamakan hipotesis induksi.
3
Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.
4
Induksi matematik berlaku seperti efek domino.
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
Contoh 1. P n(n + 1) Untuk semua n ∈ Z, ni=1 i = 1 + 2 + 3 + · · · + n = . 2 Bukti: Untuk n = 1, pernyataan tebuka S(n) :
n X
i = 1 + 2 + 3 + ··· + n =
i=1
n(n + 1) 2
P 1(1 + 1) akan menjadi S(1) : 1i=1 i = 1 = . Jadi S(1) benar 2 dan kita telah menunjukkan langkah basis.
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
Contoh 1. Selanjutnya, asumsikan hasilnya benar untuk n = k, kita akan membangun langkah induksi dengan menunjukkan bahwa kebenaran untuk S(k) ”memaksa” kita untuk menerima kebenaran untuk S(k + 1). Untuk menunjukkan kebenaran untuk S(k + 1), kita harus menunjukkan bahwa Pk+1 (k + 1)(k + 2) i=1 i = 2 Kita lakukan sebagai berikut: Pk+1 i=1
i = 1 + 2 + 3 + · · · + k + (k + 1) P = ( ki=1 i) + (k + 1) k(k + 1) = + (k + 1) 2 k(k + 1) 2(k + 1) = + 2 2 n(n + 1) = 2
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
Contoh 2. Buktikan bahwa untuk n ∈ Z+ , Bukti: Di sini kita tuliskan S(n) :
n X
i2 =
i=1
Pn
2 i=1 i
=
n(n + 1)(2n + 1) 6
n(n + 1)(2n + 1) 6
Langkah basis: Untuk S(1), kita peroleh: 1 X
i2 = 12 = 1 =
i=1
1(1 + 1)(2(1) + 1) 6
Jadi S(1) benar.
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
Contoh 2. Langkah induksi: Asumsikan bahwa S(k) benar untuk suatu k ∈ Z+ , yaitu k X
i2 =
i=1
k(k + 1)(2k + 1) 6
Dari asumsi ini, akan ditunjukkan bahwa S(k + 1) :
k+1 X i=1
i2 =
(k + 1)((k + 1) + 1)(2(k + 1) + 1) 6
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
Contoh 2. Langkah induksi: Pk+1 i=1
i2 = 12 + 22 + 32 + · · · + k 2 + (k + 1)2 Pk 2 2 = i=1 i + (k + 1) k(k + 1)(2k + 1) = [ ] + (k + 1)2 6 k(2k + 1) + (k + 1)] = (k + 1)[ 6 2 2k + 7k + 6 = (k + 1)[ ] 6 (k + 2)(2k + 3) = (k + 1)[ ] 6 (k + 1)((k + 1) + 1)(2(k + 1) + 1) = 6
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
Contoh 3. Buktikan bahwa untuk n ∈ Z+ , Bukti: Di sini kita tuliskan S(n) :
n X
Pn
i=1 (2i
− 1) = n2
(2i − 1) = n2
i=1
Langkah basis: Untuk S(1), kita peroleh: 1 X
(2i − 1) = 2(1) − 1 = 2 − 1 = 1 = 12
i=1
Jadi S(1) benar.
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
Hasilkali Kartesian
Contoh 3. Langkah induksi: Asumsikan bahwa S(k) benar untuk suatu k ∈ Z+ , yaitu k X (2i − 1) = k 2 i=1
Dari asumsi Pini, akan ditunjukkan2 bahwa S(k + 1) : k+1 i=1 (2i − 1) = (k + 1) Pk+1
i=1 (2i
− 1) = = = = =
1 + 3 + 5 + · · · + (2k − 1) + [2(k + 1) − 1] Pk i=1 (2i − 1) + [2(k + 1) − 1] k 2 + [(2(k + 1) − 1] k 2 + 2k + 1 (k + 1)2
Jadi S(n) benar untuk semua n ≥ 1.
[email protected]
INF-104 Matematika Diskrit
Induksi Matematika
[email protected]
Hasilkali Kartesian
INF-104 Matematika Diskrit
Induksi Matematika
[email protected]
Hasilkali Kartesian
INF-104 Matematika Diskrit
Induksi Matematika
[email protected]
Hasilkali Kartesian
INF-104 Matematika Diskrit
Induksi Matematika
[email protected]
Hasilkali Kartesian
INF-104 Matematika Diskrit
