Induksi matematika

-  merupakan teknik pembuktian yang sangat penting

-  dipergunakan secara luas untuk membuktikan pernyataan yang berkaitan dengan obyek diskrit.

  (kompleksitas algoritma, teorema mengenai graf, identitas dan ketidaksamaan yang melibatkan 

  bilangan bulat, dsb).

- tidak dapat digunakan untuk menemukan rumus atau teorema, tetapi hanya untuk melakukan pembuktian.

Teknik untuk membuktikan proposisi dalam bentuk "n P(n), dengan semesta pembicaraan adalah himpunan bilangan bulat positif.

Suatu bukti dengan menggunakan induksi matematika bahwa

“P(n) benar untuk setiap n bilangan bulat positif“

terdiri dari tiga langkah:

1.Langkah basis:

  Tunjukkan bahwa P(1) benar.

2.Langkah induktif:

  Tunjukkan bahwa P(k)       P(k + 1) benar untuk setiap k.

  P(k) untuk suatu k tertentu disebut hipotesa induksi.

Konklusi: "n P(n) bernilai benar.

Contoh:

Tunjukkan bahwa n < 2n untuk setiap bilangan bulat positif n.

Solusi:

Misalkan P(n): proposisi “n < 2n.”

1.Langkah basis:

  P(1) benar, karena 1 < 21 = 2.

2.Langkah induktif:

Asumsikan bahwa P(k) benar untuk semua k, yaitu

 k < 2k. 

Kita perlu menunjukkan bahwa P(k + 1) benar, yaitu

k + 1 < 2k+1

Kita mulai dari k < 2k

k + 1 < 2k + 1 £ 2k + 2k = 2k+1

Jadi, jika k < 2k maka k + 1 < 2k+1

3.Konklusi:

Jadi, n < 2n benar untuk setiap n bilangan bulat positif.

Akhir dari bukti.

Induksi Kuat(Prinsip kedua dari induksi matematika)

Terdapat bentuk lain dari induksi matematika yang sering dipergunakan dalam bukti. 

Teknik ini dinamakan Induksi Kuat atau Prinsip kedua dari induksi matematika

1.Langkah basis:

Tunjukkan bahwa P(0) benar.

2.Langkah induktif:

Tunjukkan bahwa jika P(0) dan P(1) dan … dan P(k) benar, maka P(k + 1) untuk setiap kÎN.

3.Konklusi: "n P(n) bernilai benar. 

Contoh

Tunjukkan bahwa setiap bilangan bulat yang lebih besar dari 1 dapat dituliskan sebagai hasil kali

bilangan-bilangan prima.

Solusi:

P(n): proposisi “setiap bilangan bulat yang lebih besar dari 1 dapat dituliskan sebagai hasil kali bilangan-bilangan prima”.

1.Langkah basis:

P(2) benar, karena 2 adalah hasil kali dari satu bilangan prima, dirinya sendiri. 

2.Langkah induktif:

 Asumsikan P(j) benar untuk semua bilangan bulat j, 1 < j²k.

 Harus ditunjukkan bahwa P(k+1) juga benar.

Ada dua kasus yang mungkin:

   •Jika (k + 1) bilangan prima, maka jelas P(k + 1) benar.

    •Jika (k + 1) bilangan komposit, (k+1) dapat ditulis sebagai perkalian dua buah bilangan bulat  a dan

      b sehingga 2 £ a £ b < k + 1. Oleh hipotesa induksi, a dan b keduanya dapat dituliskan sebagai hasil kali bilangan prima. Jadi, k + 1 = a × b dapat ditulis sebagai hasil kali bilangan prima.

3.Konklusi:

“Setiap bilangan bulat yang lebih besar dari 1 dapat dituliskan sebagai hasil kali bilangan-bilangan prima”.

Akhir dari bukti.