Matematika Diskrit : Prinsip Induksi Sederhana

Prinsip Induksi Sederhana

Misalkan p(n) adalah pernyataan perihal bilangan bulat positif. Kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Untuk membuktikan pernyataan ini, kita hanya perlu menunjukkan bahwa:

  1. p(1) benar
  2. jika p(n) benar, maka p(n + 1) juga benar, untuk setiap n โ‰ฅ 1

Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah induksi. Langkah induksi berisi asumsi (andaian) yang menyatakan bahwa p(n) benar. Asumsi tersebut dinamakan hipotesis induksi.

Bila kita sudah bisa menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.

Induksi matematik berlaku seperti efek domino. Untuk merobohkan semua domino, cukup mendorong domino pertama. Domino pertama akan mendorong domino kedua. Domino kedua akan mendorong domino ketiga, demikian seterusnya.


Contoh Pembuktian Pertama

Contoh 1

Buktikan bahwa jumlah n bilangan bulat positif pertama adalah n(n + 1)/2.

Penyelesaian:

Misalkan p(n) menyatakan proposisi bahwa jumlah n bilangan bulat positif pertama adalah n(n+1)/2 , yaitu

1 + 2 + 3 + โ€ฆ + n = n(n + 1)/2

Kita harus membuktikan kebenaran proposisi ini dengan dua langkah induksi sebagai berikut:

(i) Basis induksi: p(1) benar, karena untuk n = 1 kita peroleh

1 = 1(1 + 1)/ 2

= 1(2)/ 2

= 2/2

= 1

(ii) Langkah induksi: Misalkan p(n) benar, yaitu asumsikan bahwa

1 + 2 + 3 + โ€ฆ + n = n(n + 1)/2 adalah benar (hipotesis induksi).

Kita harus memperlihatkan bahwa p(n + 1) juga benar, yaitu

1 + 2 + 3 + โ€ฆ + n+(n+1) = (n + 1)[(n + 1) + 1]/2

Untuk membuktikan ini, tunjukkan bahwa

1 + 2 + 3 + โ€ฆ + n + (n + 1)= (1 + 2 + 3 + โ€ฆ + n) + (n +1)

= [n (n + 1)/2 ] + (n + 1)

= (n + 1) [n/2 + 1]

= (n + 1) + [n/2 + 2/2]

= (n + 1) (n + 2)/2

= (n + 1) [(n + 1) + 1]/2

Karena langkah (i) dan (ii) telah dibuktikan benar, maka terbukti bahwa untuk semua bilangan bulat positif n, 1 + 2 + 3 + โ€ฆ + n = n(n + 1)/2.


Contoh 2

Gunakan induksi matematik untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n2

Penyelesaian:

(i) Basis induksi: Untuk n = 1, jumlah satu buah bilangan ganjil positif pertama adalah 1= 12. Ini benar karena jumlah satu buah bilangan ganjil positif pertama adalah 1.

(ii) Langkah induksi: Andaikan p(n) benar, yaitu pernyataan

1 + 3 + 5 + โ€ฆ + (2n โ€“ 1) = n2

adalah benar (hipotesis induksi) [catatlah bahwa bilangan ganjil positif ke-n adalah (2n โ€“ 1)]. Kita harus memperlihatkan bahwa p(n +1) juga benar, yaitu

1 + 3 + 5 + โ€ฆ + (2n โ€“ 1) + (2n + 1) = (n + 1)2 juga benar.

Hal ini dapat kita tunjukkan sebagai berikut:

1 + 3 + 5 + โ€ฆ + (2n โ€“ 1) + (2n + 1) = [1 + 3 + 5 + โ€ฆ + (2n โ€“ 1)] + (2n + 1) = n2 + (2n + 1)

= n2 + 2n + 1
= (n + 1)2

Karena langkah basis dan langkah induksi keduanya telah diperlihatkan benar, maka jumlah n buah bilangan ganjil positif pertama adalah n2.


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Induksi Matematika, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Sumber: Materi Kuliah Matematika Diskrit Dr. Ir. Rinaldi Munir, MT.

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up