Matematika Diskrit : Prinsip Induksi yang Dirampatkan

Prinsip Induksi yang Dirampatkan

Prinsip induksi sederhana hanya bisa dipakai untuk n ≥ 1. Untuk sembarang nn0 kita menggunakan prinsip induksi yang dirampatkan (generalized induction principle).

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

  1. p(n0) benar
  2. jika p(n) benar maka p(n+1) juga benar, untuk semua bilangan bulat nn0

Contoh 1

Untuk semua bilangan bulat tidak-negatif n, buktikan dengan induksi matematik bahwa 20 + 21 + 22 + … + 2n = 2n+1-1

Penyelesaian:

(i) Basis induksi: Untuk n = 0 (bilangan bulat tidak negatif pertama), kita peroleh 20 = 20+1 – 1.

Ini jelas benar, sebab 20 = 1 = 20+1 – 1

= 21 – 1

= 2 – 1

= 1

(ii) Langkah induksi: Andaikan bahwa p(n) benar, yaitu 20 + 21 + 22 + … + 2n = 2n+1-1

adalah benar (hipotesis induksi). Kita harus menunjukkan bahwa p(n +1) juga benar, yaitu

20 + 21 + 22 + … + 2n + 2n+1 = 2(n+1) + 1-1

juga benar. Ini kita tunjukkan sebagai berikut:

20 + 21 + 22 + … + 2n + 2n+1 = (20 + 21 + 22 + … + 2n) + 2n+1

= (2n+1 – 1) + 2n+1 (hipotesis induksi)

= (2n+1 + 2n+1) – 1

= (2 . 2n+1) – 1

= 2n+2-1

= 2(n+1) + 1 – 1

Karena langkah (i) dan (ii) keduanya telah diperlihatkan benar, maka untuk semua bilangan bulat tidak negatif n, terbukti bahwa 20 + 21 + 22 + … + 2n = 2n+1 -1

Contoh 2

Untuk semua n ≥ 1, buktikan dengan induksi matematik bahwa n3 + 2n adalah kelipatan 3.

Penyelesaian:

(i) Basis induksi: Untuk n = 1, maka 13 + 2(1) = 3 adalah kelipatan 3. Jadi, p(1) benar.

(ii) Langkah induksi: Misalkan p(n) benar, yaitu proposisi n3 + 2n adalah kelipatan 3 (hipotesis induksi). Kita harus memperlihatkan bahwa p(n + 1) juga benar, yaitu (n + 1)3 + 2(n + 1) adalah kelipatan 3.

Hal ini dapat kita tunjukkan sebagai berikut:

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

= (n3 + 2n) + 3n2 + 3n + 3

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

Perhatikan bahwa:

  • (n3 + 2n) adalah kelipatan 3 (dari hipotesis induksi)
  • 3(n2 + n + 1) juga kelipatan 3
  • maka (n3 + 2n) + 3(n2 + n + 1) adalah jumlah dua buah bilangan kelipatan 3
  • sehingga (n3 + 2n)+3(n2 + n + 1) juga kelipatan 3.

Karena langkah (i) dan (ii) sudah diperlihatkan benar, maka terbukti bahwa untuk semua n ≥ 1, n3 + 2n adalah kelipatan 3.


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