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 ³n₀. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:

          1. p(n₀) benar, dan

          2. jikap(n) benarmakap(n+1) jugabenar,

          untuksemuabilanganbulatn³n₀,

Pada gambar diatas dapat ditunjukkan terdapat dua bagian yaitu segitiga P₁P_nP_n+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 ³ n₀. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:

          1.  p(n₀) benar, dan

          2. jika p(n₀ ), p(n₀+1), …, p(n) benarmaka p(n+1) juga benar untuk semua bilangan bulat  n ³ n₀,.

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) = 1² + 2² + 3² + … + n² = 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)²

           = k(k+1)(2k + 1)/6 + (k² + 2k + 1)

           = (2k³ + 3k² + k)/6 + 6 (k² + 2k + 1) / 6

           = (2k³ + 3k² + k + 6 (k² + 2k + 1)) / 6

           = (2k³ + 9k² + 13k + 1) /6

           = (k+1)(k+2)(2k+3)/6   …………. Terbukti