MATEMATIKA DISKRIT - INDUKSI MATEMATIKA

Induksi Matematika

Definisi Induksi Matematika

Induksi matematika (mathematical induction) adalah metode pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu pernyataan yang diberikan dalam bentuk bilangan asli. Akan tetapi sebelum membahas mengenai induksi matematika, kita akan membahas suatu prinsip yang digunakan untuk membuktikan induksi matematika, yaitu prinsip terurut rapi (well-ordering principle) dari bilangan asli. Seperti kita ketahui, himpunan bilangan asli adalah himpunan yang memiliki anggota 1, 2, 3, … yang dapat dituliskan sebagai berikut.

Konsep Dasar Induksi Matematika

1.      Buktikan bahwa rumus tersebut benar untuk nilai n dasar (pada contoh di atas, buktikan untuk n=1).

2.      Buktikan bahwa jika rumus tersebut benar untuk n=k, maka rumus tersebut juga benar untuk n=k+1.

Prinsip Induksi Matematika

•  Prinsip Terurut Rapi Bilangan Asli

Setiap himpunan bagian yang tidak kosong dari N memiliki anggota terkecil.

• Prinsip Induksi Matematika

Misalkan S adalah himpunan bagian N yang memiliki 2 sifat:
(1) S memiliki anggota bilangan 1; dan
(2) Untuk setiap k anggota N, jika k anggota S, maka k + 1 anggota S.
Maka diperoleh S = N.

·         Prinsip Induksi Matematika (versi kedua)
Misalkan n₀ anggota N dan misalkan P(n) merupakan pernyataan untuk setiap bilangan asli n ≥ n₀. Apabila:
(1) Pernyataan P(n₀) benar;
(2) Untuk setiap k ≥ n₀, jika P(k) benar mengakibatkan P(k + 1) benar.
Maka P(n) benar untuk semua n ≥ n₀.

Contoh

1.        Membuktikan Pertidaksamaan dengan Induksi Matematika

Buktikan bahwa

untuk semua bilangan bulat positif n ≥ 3.

Pembahasan Misalkan P(n) menyatakan (n + 1)² < 2n².

1.    Pernyataan P(3), yaitu

dengan jelas bernilai benar.

2.   Anggap P(k): (k + 1)² < 2k² bernilai benar, kita harus menunjukkan bahwa P(k + 1) juga bernilai benar, yaitu [(k+1) + 1]² < 2(k + 1)². Untuk k ≥3, kita memperoleh

Sehingga kita telah menunjukkan kebenaran pernyataan jika P(k) benar maka P(k + 1). Oleh karena itu, berdasarkan Langkah 1 dan 2, dengan induksi matematika kita dapat menyimpulkan bahwa P(n) benar untuk semua bilangan bulat positif n ≥ 3.

2.        Buktikan bahwa :

2 + 4 + 6 +8 +10 + 12 + 14 + ....... + 2n = n² + 2 

Pembahasan :

⇒Pertama, buktikan terlebih dahulu nilai untuk n = 1. 

Jika kita masukan nilai n = 1, nilai fungsi tersebut menjadi 1² + 1 = 2 (benar). Kemudian kita sesuaikan dengan persamaan yang di berada di ruas kanan yaitu n² + 2 , ternyata hasil yang diperoleh sama yaitu 2 (dua). 

⇒ Kedua, kita buktikan untuk n = k. 

sehingga deret penjumlahan di atas akan menjadi :

2 + 4 + 6 +8 +10 + 12 + 14 + ....... + 2n = n² + n  

2 + 4 + 6 +8 +10 + 12 + 14 + ....... + 2k = k² + k 

Untuk n = k ini kita anggap bahawa bernilai benar.


⇒ Ketiga, kita buktikan untuk n = k + 1

Apabila disubstitusi nilai n = k +1 ke persamaan maka diperoleh deret seperti berikut:

2 + 4 + 6 +8 +10 + 12 + 14 + ....... + 2n = n² + n 

2 + 4 + 6 +8 +10 + 12 + 14 + ....... + 2k + 2(k + 1) = (k + 1)² + (k + 1)

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

ingat bahwa:

2 + 4 + 6 +8 +10 + 12 + 14 + ....... + 2k = k² + k

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

Setelah itu, kita buktikan bahwa ruas kiri harus sama dengan ruas kanan. Sebagai acuan dalam pembuktiaan yakni persamaan yang ada disebelah kanan. Itu artinya persamaan yang ada disebelah kiri harus diusahakan sama dengan ruas kanan. Sehingga :

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

Supaya persamaan di ruas kiri berbentuk persamaan kuadrat seperti di ruas kanan, maka persamaan di ruas kiri kita atur. penyelesaiannya sebagai berikut :

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

sehingga :

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

(k + 1)² + (k + 1) = (k + 1)² + (k + 1) 

Sampai ditahap ini dapat kita perhatikan bahawa ruas kiri sudah sama dengan ruas kanan dan bentuk persamaannya bersesuain saat kita memasukkan nilai n = k.

Karena ketiga persamaan penjumlahan di atas sudah benar dari ketiga langkah yang diselesaikan, maka dapat kita simpulkan bahwa penjumlahan diperoleh:

2 + 4 + 6 +8 +10 + 12 + 14 + ....... + 2n = n² + n   terbukti benar .