INDUKSI MATEMATIKA

Induksi Matematika

Induksi Matematika adalah cara standar dalam membuktikan bahwa sebuah pernyataan tertentu berlaku untuk setiap bilangan asli. Pembuktian dengan cara ini terdiri dari dua langkah, yaitu:

1.     Menunjukkan bahwa pernyataan itu berlaku untuk bilangan 1.

2.     Menunjukkan bahwa jika pernyataan itu berlaku untuk bilangan n, maka pernyataan itu juga berlaku untuk bilangan n + 1.

Misalkan akan dibuktikan suatu pernyataan bahwa jumlah n bilangan asli pertama, yaitu 1+2+...+n, adalah sama dengan n(n+1) /2. Untuk membuktikan bahwa pernyataan itu berlaku untuk setiap bilangan asli, langkah-langkah yang dilakukan adalah sebagai berikut:

1.     Menunjukkan bahwa pernyataan tersebut benar untuk n = 1. Jelas sekali bahwa jumlah 1 bilangan asli pertama adalah 1(1+1) /2 = 1. Jadi pernyataan tersebut adalah benar untuk n = 1.

2.     Menunjukkan bahwa jika pernyataan tersebut benar untuk n = k, maka pernyataan tersebut juga benar untuk n = k+1. Hal ini bisa dilakukan dengan cara:

·        Mengasumsikan bahwa pernyataan tersebut benar untuk n = k, yaitu

·        Menambahkan k + 1 pada kedua ruas, yaitu

·        Dengan menggunakan manipulasi aljabar, diperoleh

·        Dengan demikian

·        Jadi pernyataan tersebut benar untuk n = k + 1.

3.     Dengan induksi matematika dapat disimpulkan bahwa pernyataan tersebut berlaku untuk setiap bilangan asli n.

Secara formal Induksi Matematika ini bisa didefinisikan sebagai berikut.

Definisi :

Misalkan untuk setiap bilangan asli n kita mempunyai pernyataan P(n) yang bisa benar atau salah. Misalkan :

1.     P(1) benar.

2.     Jika P(n) benar, maka P(n + 1) benar.

Sehingga P(n) benar untuk setiap bilangan asli n.

Langkah 1 disebut dengan Langkah Dasar, sedangkan Langkah 2 disebut dengan Langkah Induktif.

Jika pada Langkah Induktif yang diasumsikan adalah pernyataan P(i) benar untuk setiap bilangan i ≤ n, maka perumusan induksi matematika seperti ini disebut Bentuk Kuat Induksi Matematika.

Contoh :

Gunakan induksi matematika untuk membuktikan bahwa

n! ≥ 2n−1

untuk setiap n = 1,2,....

1.     Akan ditunjukkan bahwa n! ≥ 2n−1 benar untuk n = 1.

Jelas sekali bahwa 1! = 1 ≥ 1 = 20 = 21−1.

2.     Asumsikan bahwa n! ≥ 2n−1 adalah benar untuk n = k.

3.     Akan ditunjukkan bahwa n! ≥ 2n−1 juga benar untuk n = k + 1, yaitu (k + 1) ≥ 2^(k+1)−1.

Terbukti bahwa (k+1) ≥ 2^(k+1)−1. Karena Langkah Dasar dan Langkah Induktif terbukti, maka dapat disimpulkan bahwa

n! ≥ 2n−1

untuk setiap n = 1,2,....