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 \in \mathbb{N} mempunyai pengikut p(x) \in \mathbb{N}
  3. Dua bilangan di \mathbb{N} yang berbeda mempunyai pengikut yang berbeda.
  4. 1 bukan pengikut bilangan x \in \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 $latex 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 \in \mathbb{N} berlaku 1 + 2 + 3 + \ldots + n = \dfrac{1}{2} n(n + 1)

Basis Induksi

n = 1

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

1=1

benar

Langkah Induksi

n = k

1+2+3 \ldots + k = \dfrac{1}{2} k(k+1)

benar

Hipotesis Induksi

akan dibuktikan benar untuk n = k+1

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

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

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

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

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

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

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

Jadi benar 1+2+3 \ldots + n = \dfrac{1}{2} n(n+1) untuk setiap  n \in \mathbb{N}

Contoh 2.

Buktikan bahwa untuk setiap n \in \mathbb{N} dan n_0 \in \mathbb{N} berlaku 1 + 3 + 5 + \ldots + n(n + 1)/2 = \dfrac{1}{6} n(n + 1)(n + 2)

Basis Induksi

n=1
1^2 = \dfrac{1}{6} 1(1+1)(1+2)
1=1

benar

Langkah Induksi

n=k

1+3+5+ \ldots + k(k + 1)/2 = \dfrac{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 = \dfrac{1}{6} k(k + 1)(k + 2) + (k + 1)(k + 2)/2

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

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

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

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

Jadi benar 1 + 3 + 5 + … + n(n + 1)/2 = \dfrac{1}{6} n(n + 1)(n + 2), n \in \mathbb{N}

Contoh 3.

Buktikan bahwa untuk setiap n \in \mathbb{N} dan n_0 \in \mathbb{N} berlaku 1^3 + 2^3 + 3^3 + \ldots + n^3 = \left( \dfrac{n}{2} (n + 1) \right)^2

Basis Induksi

n=1
1^3 = \left( \dfrac{1}{2} (1+1) \right)^2
1=1

benar

Langkah Induksi

n=k

1^3 + 2^3 + 3^3 + \ldots + k^3 = \left( \dfrac{k}{2} (k+1) \right)^2

benar

Hipotesis Induksi

akan dibuktikan benar untuk n=k+1

1^3 + 2^3 + \ldots + k^3 + (k+1)^3 = \left( \dfrac{k}{2} (k+1) \right)^2 + (k+1)^3

= \dfrac{k^2}{4} (k+1)^2+(k+1)^3

= \left( \dfrac{k^2}{4}+(k+1) \right) (k+1)^2

= \left( \dfrac{k^2+4k+4}{4} \right)(k+1)^2

= \left( \dfrac{(k+2)^2}{4} \right)(k+1)^2

= \left( \dfrac{(k+2)}{2} (k+1) \right)^2

= \left( \dfrac{((k+1)+1)}{2} (k+1) \right)^2

= \left( \dfrac{(k+1)}{2}((k+1)+1) \right)^2

Jadi benar 1^3+2^3+3^3+ \ldots +n^3= \left( \dfrac{n}{2} (n+1) \right)^2, n \in \mathbb{N}

Sumber :

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

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

Iklan

20 comments on “Pembuktian dengan Induksi Matematika”

  3. kak mohon bantuannya, tentang akar bilangan kompleks
    Hitunglah : (-2+ 2i)^1/5

    kak mohon dikoreksi,..
    Z = (-2+2i)^1/5
    Z^5 = (-2+ 2i)
    W = (-2+ 2i)
    r = akar(-2^2)+(2^2) =akar 8

    tan teta = y/x =2/-2 = -1
    teta = 135 derajat = 3 pi/4
    p^n = r
    p^5 = akar 8
    p = ….*

    tsi = (teta + 2. k. pi)/ n
    tsi = (3 .pi/4 + 2.k.pi)/ 5
    k = 0, 1, 2, 3, 4

    p^n(cos n tsi + i sin n tsi) = r (cos teta + i sin teta)
    p^5(cos 5 tsi + i sin 5 tsi) = akar 8 (cos 135 + i sin 135 )
    Z = r^1/n [cos ( (teta + 2.k. pi)/n) + i sin ( (teta +2.k.pi)/n)]
    k= 0 ===> Z = … *[cos ( 3.pi/4 +2.0. 3.pi/4) / 5 + i sin ( 3.pi/4 + 2.0. 3.pi/4) ]
    = …

    kak mohon bantuannya…

    Balas

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

Tinggalkan Balasan

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

Gravatar
Logo WordPress.com

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

Foto Google+

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

Gambar Twitter

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

Foto Facebook

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

Batal

Connecting to %s