INDUKSI MATEMATIK
PENGERTIAN
n Metode pembuktian untuk pernyataan perihal bilangan bulat adalah induksi
matematik.
n Contoh :
p(n):“Jumlah bilangan bulat positif dari 1 sampai n adalah n
(n + 1)/2”.
Buktikan
p(n) benar!
n Induksi matematik merupakan teknik pembuktian yang baku di dalam matematika.
n Melalui induksi matematik kita dapat mengurangi langkah-langkah pembuktian
bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya
sejumlah langkah terbatas.
Prinsip Induksi Sederhana
n Misalkan p(n) adalah pernyataan perihal bilangan bulat positif.
n Kita ingin membuktikan bahwa p(n) benar untuk semua bilangan
bulat positif n.
n Untuk membuktikan pernyataan ini, kita hanya perlu menunjukkan bahwa:
1.
p(1) benar, dan
2. jika p(n) benar, maka p(n
+ 1) juga benar, untuk setiap n³ 1,
n Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah
induksi.
n Langkah induksi berisi asumsi (andaian) yang menyatakan bahwap(n)
benar. Asumsi tersebut dinamakan hipotesis induksi.
n Bila kitas udah menunjukkan kedua langkah tersebut benar maka kita sudah
membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.
n Induksi matematik berlaku seperti efek domino.
Prinsip Induksi
yang Dirapatkan
Misalkanp(n)
adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n)
benar untuk semua bilangan bulatn ³n0. Untuk membuktikan ini,
kita hanya perlu menunjukkan bahwa:
1. p(n0)
benar, dan
2. jikap(n) benarmakap(n+1)
jugabenar,
untuksemuabilanganbulatn³n0,
Pada gambar diatas dapat
ditunjukkan terdapat dua bagian yaitu segitiga P1PnPn+1)
dan polygon dengan n sisi
Jumlah sudut dalam poligon n sisi menurut
asumsi yaitu 180(n − 2)°dan jumlah sudut
di dalam untuk segitiga yaitu 180°.
Jadi jumlah sudut dalam dari polygon dengan
n + 1 sisi yaitu 180(n − 2)° + 180° = 180(n − 1)°.
n Karena basis dan langkah induksi benar, maka proposisi di
atas terbukti benar.
Prinsip Induksi Kuat
n Misalkanp(n) adalah pernyataan perihal bilangan bulat dan
kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ³ n0. Untuk membuktikan ini, kita hanya perlu
menunjukkan bahwa:
1.
p(n0) benar, dan
2. jika p(n0 ), p(n0+1),
…, p(n) benarmaka p(n+1) juga benar untuk semua bilangan bulat n ³ n0,.
Buktikan “Jumlah
bilangan bulat positif dari 1 sampai n adalah n(n + 1)/2”
!
Jawaban
:
·
Langkah nomer 1 : Buktikan
bahwa P(1) benar
P(1) = 1(1
+ 1)/2 = 1 ………. Terbukti
·
Langkah nomer 2 : Buktikan
bahwa jika P(n) benar, maka P(n+1) juga benar
P(n+1) = 1 + 2 + 3 + … + n +
(n+1)
(n+1)((n+1)
+1)/2 = P(n) + (n+1)
(n+1)(n+2)/2 = n(n+1)/2 + 2(n+1)/2
(n+1)(n+2)/2 = (n+2)(n+1)/2 ……. Terbukti
Contoh
Soal 2 :
Buktikan P(n) = 12 + 22 + 32
+ … + n2 = n(n+1)(2n+1)/6
untuk n > 1 !
·
Langkah nomer 1 :
P(1) = 1(1+1)(2 x 1 + 1) /
6 = 1
……. Terbukti
·
Langkah nomer 2:
Andaikan benar untuk n = k,
maka P(k) = k(k+1)(2k + 1)/6
Akan dibuktikan bahwa P(k+1)
= (k+1)(k+1+1)(2(k+1)+1)/6
= (k+1)(k+2)(2k+3)/6
Bukti bahwa P(k+1) benar :
P(k+1) = p(k) + (k+1)2
= k(k+1)(2k + 1)/6 +
(k2 + 2k + 1)
= (2k3 +
3k2 + k)/6 + 6 (k2 + 2k + 1) / 6
= (2k3 +
3k2 + k + 6 (k2 + 2k + 1)) / 6
= (2k3 +
9k2 + 13k + 1) /6
=
(k+1)(k+2)(2k+3)/6 …………. Terbukti
Tidak ada komentar:
Posting Komentar