Induksi Matematika

Dalam kasus diskrit kadang kala kita harus membuktikan bukan hanya satu atau beberapa pernyataan, tapi sampai tak berhingga pernyataan, tapi sampai tak berhingga pernyataan untuk bilangan asli. Induksi matematika merupakan teknik pembuktian yang sangat penting, dipergunakan secara luas untuk membuktikan pernyataan yang terkait dengan objek diskrit. Induksi matematika tidak dapat digunakan untuk menemukan rumus atau teorema, tetapi hanya untuk melakukan pembuktian dari teorema atau pernyataan tersebut sedemikian hingga berlaku untuk setiap bilangan asli (N).

Misalkan P(n) adalah pernyataan tentang n. kita ingin membuktikan semua P(1), P(2), P(3), ….. P(n), … tidaklah praktis sebab untuk langkah ke-n tertentu pastilah ada langkah ke-(n+1) yang masih tersisa. Oleh sebab itu di perlukan suatu metode tersendiri.
Induksi matematika adalah cara standar dalam membuktikan bahwa sebuah pernyataan tertentu berlaku untuk setiap bilangan asli.

Langkah langkah
Misalkan untuk setiap bilangan asli n kita mempunyai pernyataan P(n). pembuktian dengan induksi matematoika terdiri dari dua langkah yaitu:
1. Basis Induksi
Menunjukan bahwa pernyataan yang akan dibuktikan berlaku untuk bilangan dengan kata lain tunjukan bahwa P(1) benar.

2. Langkah Induksi
Menunjukan bahwa jika pernyataan itu berlaku untuk bilangan n maka pernyataan itu juga berlaku untuk bilangan (n+1)
Caranya:
a. Asumsikan bahwa pernyataan tersebut benar untuk n=k P(k) untuk suatu k tertentu dalam kasus ini disebut hipotesa Induksi.
b. Tunjukan bahwa jika pernyataan tersebut benar untuk n=k, maka pernyataan tersebut juga benar untuk n=(k+1)
c. Dengan terbukti (a) dan (b) maka dengan induksi matematika dapat disimpilkan bahwa pernyataan tersebut berlaku untuk setiap bilangan asli n.