Selasa, 09 Oktober 2012


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,.
Contoh Soal 1 :
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:

Poskan Komentar