INDUKSI MATEMATIKA

INDUKSI MATEMATIKA

Induksi Matematika (mathematical induction) adalah metode pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu pernyataan yang diberikan dalam bentuk bilangan asli.

Prinsip Induksi Matematika

Misalkan S adalah himpunan bagian N yang memiliki dua sifat:

1. S memiliki anggota bilangan 1

2. Untuk setiap k anggota N, jika k anggota S, maka k+1 anggota S.

Maka diperoleh S=N

Prinsip Induksi Matematika juga dapat dinyatakan sebagai berikut:

Untuk setiap n anggota N, misalkan p(n) merupakan suatu pernyataan tentang n. Apabila:

 p(1) benar untuk setiap k anggota N,  jika p(k) benar, maka p(k+1) benar.

Maka p(n) benar untuk setiap n anggota N.

Asumsi bahwa "jika p(k) benar" dinamakan hipotesis induksi.

Langkah-langkah Induksi Matematika

f(n) misalkan suatu pernyataan yang dinyatakan berlaku untuk semua bilangan asli n.

Untuk membuktikan apakah pernyataan ini bernilai benar atau tidak untuk semua bilangan asli, ada dua langkah yang dilakukan yaitu:

1. f(1) jika benar dan;

2. jika f(k) benar yang mengakibatkan f(k+1) juga benar.

Maka f(n) benar untuk setiap bilangan asli n.

contoh:

Jumlah n bilangan asli pertama.

Buktikan untuk setiap n anggota N, jumlah dari n bilangan asli pertama dirumuskan:

Bukti:
Langkah 1:



Maka pernyataan tersebut bernilai benar untuk n=1

Langkah 2:
Misalkan pernyataan tersebut bernilai benar untuk n=k, yaitu:


maka akan kita buktikan bahwa pernyataan tersebut juga benar untuk , yaitu:


Dari persamaan (*), kita tambahkan (k+1) pada kedua ruas, yaitu:








pernyataan (**) benar untuk , maka kita menyimpulkan bahwa  anggota S sehingga kondisi 2 terpenuhi. Sebagai hasilnya, menurut prinsip induksi matematika kita peroleh bahwa, atau dengan kata lain persamaan tersebut berlaku untuk semua bilangan asli.