Agu 15 2012

Pembuktian dengan Induksi Matematika


Induksi Matematika berawal pada akhir abad ke-19 yang dipelopori oleh dua orang matematikawan yaitu R. Dedekind dan G.Peano. Dedikind mengembangkan sekumpulan aksioma yang menggambarkan bilangan bulat positif. Peano memperbaiki aksioma tersebut dan memberikannya interpretasi logis. Keseluruhan aksioma tersebut dinamakan Postulat Peano. Postulat ini ditemukan sekitar tahun 1890 sebagai rumusan formula konsep bilangan asli.

Postulat Peano

  1. 1 adalah anggota \mathbb{N}
  2. Setiap anggota x \epsilon \quad \mathbb{N} mempunyai pengikut p(x) \epsilon \quad \mathbb{N}
  3. Dua bilangan di \mathbb{N} yang berbeda mempunyai pengikut yang berbeda.
  4. 1 bukan pengikut bilangan x \epsilon \quad \mathbb{N} yang manapun
  5. Jika subhimpunan S \subseteq \mathbb{N} memuat 1 dan pengikut dari setiap bilangan di S, maka S = \mathbb{N}

 

Induksi Matematika merupakan teknik pembuktian yang baku dalam matematika dan merupakan salah satu metoda/alat yang digunakan untuk membuktikan suatu pernyataan matematika, khususnya pernyataan-pernytaan yang berkaitan dengan bilangan asli atau bilangan bulat positif. Melalui Induksi Matematika ini kita dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas.

Prinsip Induksi Sederhana

Misalkan p(n) adalah proporsi prihal bilangan bulat positif dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Untuk membuktikan proporsi 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 \geq 1

sehingga p(n) benar, maka semua bilangan bulat positif n

Langkah 1 dinamakan Basis Induksi, yang digunakan untuk memperlihatkan bahwa pernyataan tersebut benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil. Sedangkan Langkah 2 dinamakan Langkah Induksi, yang berisi asumsi yang menyatakan bahwa p(n) benar. Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Kemudian kita harus menunjukkan bahwa implikasi p(n) \rightarrow p(n + 1) benar untuk setiap bilangan bulat positif. Hal ini dapat diselesaikan dengan cara memperlihatkan bahwa berdasarkan hipotesis p(n) benar maka p(n + 1) juga harus benar. Langkah pembuktian p(n + 1) bernilai benar dinamakan Hipotesis Induksi.

Contoh 1 :

Buktikan bahwa untuk setiap n \epsilon \quad \mathbb{N} berlaku 1 + 2 + 3 + … + n = \frac{1}{2} n(n + 1)

Basis Induksi

n = 1

1 = \frac{1}{2} 1(1 + 1)

1 = 1

benar

Langkah Induksi

n = k

1 + 2 + 3 + … + k = \frac{1}{2} k(k + 1)

benar

Hipotesis Induksi

akan dibuktikan benar untuk n = k + 1

1 + 2 + 3 + … + k + (k + 1) = \frac{1}{2} k(k + 1) + (k + 1)

= \frac{k(k+1)}{2} + \frac{2(k+1)}{2}

= \frac{k^2+k}{2} + \frac{2k+2}{2})

= \frac{k^2+k+2k+2}{2}

= \frac{k^2+3k+2}{2}

= \frac{(k+1)(k+2)}{2}

= \frac{1}{2}(k+1)((k+1)+1)

Jadi benar 1 + 2 + 3 + … + n = \frac{1}{2} n(n + 1) untuk setiap n \epsilon \quad \mathbb{N}

Contoh 2 :

Buktikan bahwa untuk setiap n \epsilon \quad \mathbb{N} dan n0 \epsilon \quad \mathbb{N} berlaku 1 + 3 + 5 + … + n(n + 1)/2 = \frac{1}{6} n(n + 1)(n + 2)

Basis Induksi

n = 1

12 = \frac{1}{6} 1(1 + 1)(1 + 2)

1 = 1

benar

Langkah Induksi

n = k

1 + 3 + 5 + … + k(k + 1)/2 = \frac{1}{6} k(k + 1)(k + 2)

benar

Hipotesis Induksi

akan dibuktikan benar untuk n = k + 1

1 + 3 + … + k(k + 1)/2 + (k + 1)(k + 2)/2 = \frac{1}{6} k(k + 1)(k + 2) + (k + 1)(k + 2)/2

= \frac{k(k+1)(k+2)}{6} + \frac{3(k+1)(k+2)}{6}

= \frac{k^3+3k^2+2k}{6} + \frac{3k^2+9k+6}{6}

= \frac{k^3+6k^2+11k+6}{6}

= \frac{(k+1)(k+2)(k+3)}{6}

Jadi benar 1 + 3 + 5 + … + n(n + 1)/2 = \frac{1}{6} n(n + 1)(n + 2) n \epsilon \quad \mathbb{N}

Sumber :

Arifin, A, 2000, Aljabar, ITB Bandung Press, Bandung.

Munir, R., 2009, Matematika Diskrit, Informatika, Bandung.

About these ads

9 comments on “Pembuktian dengan Induksi Matematika”

  1. Ping-balik: Fibonacci dan Induksi Matematika | Math IS Beautiful

  2. Ping-balik: Pembuktian Langsung | Math IS Beautiful

  5. Bro kayaknya postulat diatas agak rancu sbnernya bilangan 0 bukan 1 itu yang di postulat 1 dan 4 … Soalanya aq bca di buku filsafat dan sejarah matematika karangan sukardjo.

    Balas

  6. kak mau tanya nih, soal tentang induksi matematika saya kurang ngerti mohon bantuannya…
    Buktikan dengan prinsip induksi matematika bahwa:
    a) untuk semua n € Z+ (n anggota bil. bulat positif), n>3 berlaku 2^n < n!
    Mohon bantuan penyelesaiannya…

    Balas

    • asumsikan benar utk n=4.
      2^4 = 2.2.2.2 = 16
      4! = 1.2.3.4 = 24
      .:. 2^4 < 4!
      benar utk n, yaitu 2^n < n!
      adb : benar utk n+1
      2^(n+1) = 2.2^n
      (n+1)! = (n+1)n!
      perhatikan bahwa 2^n < n!, berakibat 2.2^n 3, maka diperoleh 2.2^n < 2.n! < (n+1).n! = (n+1)!
      .:. 2^(n+1) < (n+1)!

      Balas

  7. Ping-balik: Program Delphi Bilangan Fibonacci

Berikan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. ( Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. ( Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. ( Logout / Ubah )

Batal

Connecting to %s