Induksi Matematika (Matematika Diskret)
INDUKSI MATEMATIKA
Induksi matematika (mathematical induction) adalah
metode pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu
pernyataan yang diberikan dalam bentuk bilangan asli. Akan tetapi sebelum
membahas mengenai induksi matematika, kita akan membahas suatu prinsip yang
digunakan untuk membuktikan induksi matematika, yaitu prinsip terurut rapi (well-ordering
principle) dari bilangan asli. Seperti kita ketahui, himpunan bilangan asli
adalah himpunan yang memiliki anggota 1, 2, 3, … yang dapat dituliskan sebagai
berikut.
N = {1,2,3,..}
Lalu,Bagaimana dengan n=6? Gampang, tinggal kita
hitung aja lagi begini:
1+2+3+4+5+6 = 21.
Prinsip
Induksi Sederhana
Misalkan p(n) adalah proposisi bilangan bulat positif
dan ingin dibuktikan bahwa p(n) adalah benar untuk semua bilangan bulat
positif n. Maka langkah-langkahnya adalah sebagai berikut :
· n p(n)
benar
· n Jika
p(n) benar, maka p(n+1) juga benar untuk setiap n ³ 1
Sehingga p(n) benar untuk semua
bilangan bulat positif n.
Contoh :
Tunjukkan bahwa untuk n ³ 1, 1+2+3+…+n = n(n+1)/2 melalui induksi matematika
: 1+2+3+…+n+(n+1) = (1+2+3+…+n)+(n+1)
Tunjukkan bahwa untuk n ³ 1, 1+2+3+…+n = n(n+1)/2 melalui induksi matematika
: 1+2+3+…+n+(n+1) = (1+2+3+…+n)+(n+1)
= [n(n+1)/2]+(n+1)
= [(n2+n)/2]+(n+1)
= [(n2+n)/2]+[(2n+2)/2]
= (n2+3n+2)/2
= (n+1)(n+2)/2
= (n+1)[(n+1)+1]/2
Langkah (i) dan (ii) dibuktikan benar, maka untuk
semua bilangan bulat positif n, terbukti bahwa untuk semua n ³ 1,
1+2+3+…+n = n(n+1)/2 .
Contoh soal :
Buktikan untuk setiap n anggota N,
jumlah dari n bilangan asli pertama diberikan oleh rumus,
Bukti Kita
akan mencoba membuktikan pernyataan di atas dengan Prinsip Induksi Matematika
yang dibahas di awal. Misalkan S adalah himpunan yang memuat n anggota Nsedemikian
sehingga rumus di atas bernilai benar. Kita harus menguji apakah kondisi (1)
dan (2) pada Prinsip Induksi Matematika terpenuhi. Jika n = 1, maka 1
= 1/2 ∙ 1 ∙ (1 + 1) sehingga 1 anggota S, dan (1) terpenuhi. Selanjutnya,
andaikan k anggota S maka kita akan menunjukkan k +
1 juga akan menjadi anggota S. Jika k angota S, maka
Jika kita menambahkan k + 1 pada persamaan
di atas, maka akan diperoleh
Karena persamaan di atas merupakan pernyataan
untuk n = k + 1, maka kita menyimpulkan bahwa k +
1 anggota S. Sehingga, kondisi (2) terpenuhi. Sebagai hasilnya, menurut
Prinsi Induksi Matematika kita memperoleh bahwa S = N, atau
dengan kata lain persamaan tersebut berlaku untuk semua bilangan asli.
Prinsip
Terurut Rapi Bilangan Asli
Setiap himpunan bagian yang tidak kosong dari N memiliki anggota terkecil.
Setiap himpunan bagian yang tidak kosong dari N memiliki anggota terkecil.
Prinsip
Induksi Matematika
Misalkan S adalah himpunan bagian N yang memiliki 2 sifat:
(1) S memiliki anggota bilangan 1; dan
(2) Untuk setiap k anggota N, jika k anggota S, maka k + 1 anggota S.
Maka diperoleh S = N.
Misalkan S adalah himpunan bagian N yang memiliki 2 sifat:
(1) S memiliki anggota bilangan 1; dan
(2) Untuk setiap k anggota N, jika k anggota S, maka k + 1 anggota S.
Maka diperoleh S = N.
Komentar
Posting Komentar