INDUKSI MATEMATIKA

Induksi Matematika

A.      Pengertian Induksi Matematika

Induksi Matematika merupakan suatu teknik yang dikembangkan untuk membuktikan pernyataan. Induksi matematika menjadi alat pembuktian matematis yang digunakan untuk membuktikan pernyataan atau proses yang melibatkan perhitungan bilangan asli yang berulang seperti deret aritmatika, deret geometris, ataupun sigma bilangan.

Pembuktian menggunakan induksi matematika dilakukan dengan dua langkah, yaitu:

1. Melakukan pembuktian kasus dasar (base case), yaitu membuktikan bahwa sebuah pernyataan (fungsi) matematika atau algoritma bernilai benar jika diaplikasikan pada bilangan pertama yang sah sesuai dengan spesifikasi fungsi atau algoritma tersebut.
2. Melakukan induksi, yaitu membuktikan bahwa kebenaran dari fungsi P(k+1) jika kebenaran fungsi P(k)diketahui.

Dengan membuktikan kedua hal tersebut, kita dapat mengambil kesimpulan bahwa sebuah fungsi matematika atau algoritma bernilai benar untuk semua bilangan asli. Jika diimplementasikan dengan tepat, induksi matematika dapat juga digunakan untuk membuktikan kebenaran algoritma rekursif seperti penelusuran pohon (tree).

B.      Kelebihan dan Kelemahan Induksi Matematika

Induksi Matematika digunakan untuk membuktikan suatu pernyataan. Di sini metode yang digunakan dalam pembuktian adalah metode yang bersifat umum atau general. Di sini induktif sangat diperlukan di mana suatu ilmu pengetahuan tidak akan berkembang tanpa adanya pembuktian atau penalaran yang bersifat umum di mana bukti tersebut mudah diserap. Induksi matematikan sendiri mudah dipahami dibandingkan dengan pembuktian yang bersifat khusus.

Di sisi lain, meskipun memiliki kelebihan, terdapat juga kekurangan pada induksi di mana ketika kita mendapat kesimpulan dan pembuktian dari induksi, hasilnya bisa saja salah di waktu-waktu kemudian. Hal ini wajar karena ilmu pengetahuan berkembang terus. Dari hal ini bisa diketahui bahwa hasil yang didapat dari induksi tidaklah benar sepenuhnya.

C.      Prinsip Induksi Matematika

Induksi matematik merupakan teknik pembuktian yang baku di dalam matematika.

Melalui induksi matematik kita dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas.

-           Misalkan p(n) adalah pernyataan perihal bilangan bulat positif.

-           Kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.

-           Untuk membuktikan pernyataan ini, kita hanya perlu menunjukkan bahwa:

            1.   p(1) benar, dan

            2.  jika p(n) benar, maka p(n + 1) juga benar, untuk setiap n ³ 1,

-           Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah induksi.

-           Langkah induksi berisi asumsi (andaian) yang menyatakan bahwa p(n) benar.       Asumsi tersebut dinamakan hipotesis induksi.

-           Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah         membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.

D.      Pembuktian Induksi Matematika

Contoh 1 :

Buktikan bahwa :

1 + 2 + 3 + … + n = ½ n(n+1)

untuk setiap n bilangan integer positif

Jawab :

q  Basis : Untuk n = 1 akan diperoleh :

      1 = ½ 1 . (1+1) ® 1 = 1

q  Induksi : misalkan untuk n = k  asumsikan 1 + 2 + 3 + …+ k = ½ k (k+1)

q  adib. Untuk n = k+1 berlaku

1 + 2 + 3 + …+ (k+1) = ½ (k+1) (k+2)

Jawab :

q  1 + 2 + 3 + …+ (k+1) = (k+1) (k+2) / 2

1 + 2 + 3 + …+ k + (k+1) = (k+1) (k+2) / 2

 

k (k+1) / 2 + (k+1) = (k+1) (k+2) / 2

(k+1) [ k/2 +1 ] = (k+1) (k+2) / 2

(k+1) ½ (k+2) = (k+1) (k+2) / 2

(k+1) (k+2) / 2 = (k+1) (k+2) / 2

q        Kesimpulan : 1 + 2 + 3 + …+ n = ½ n (n +1)

Untuk setiap bilanga bulat positif n

Contoh 2 :

Buktikan bahwa :

1 + 3 + 5 + … + n = (2n - 1) = n²

untuk setiap n bilangan bulat positif

Jawab :

q  Basis : Untuk n = 1 akan diperoleh :

      1 = 1² ® 1 = 1

q  Induksi : misalkan untuk n = k   asumsikan 1 + 3 + 5 + …+ (2k – 1) = k²

q  adib. Untuk n = k + 1 berlaku

q   

1 + 3 + 5 + …+ (2 (k + 1) – 1) = (k + 1)²

1 + 3 + 5 + …+ (2k + 1) = (k + 1)²

1 + 3 + 5 + …+ ((2k + 1) – 2) + (2k + 1) = (k + 1)²

1 + 3 + 5 + …+ (2k   - 1) + (2k + 1 ) = (k + 1)²

 

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

                        k ² + 2K + 1                 = k ² + 2K + 1

Kesimpulan : 1 + 3 + 5 + … + n = (2n - 1) = n²

Untuk setiap bilangan bulat positif n

Contoh 3 :

Buktikan bahwa :

N ³ + 2n adalah kelipatan 3

untuk setiap n bilangan bulat positif

Jawab :

q  Basis : Untuk n = 1 akan diperoleh :

      1 = 1³ + 2(1)  ® 1 = 3 , kelipatan 3

q  Induksi : misalkan untuk n = k  asumsikan k ³ + 2k  = 3x

q  adib. Untuk n = k + 1 berlaku

(k + 1)³  + 2(k + 1) adalah kelipatan 3

(k ³ + 3k ² + 3 k+1) + 2k + 2

(k ³ + 2k) + (3k ² + 3k + 3)

(k ³ + 2k) + 3 (k ² + k + 1)

            Induksi

3x + 3 (k ² + k + 1)

3 (x + k ² + k + 1)

Kesimpulan : N ³ + 2n adalah kelipatan 3

Untuk setiap bilangan bulat positif n

E. Induksi Pembuktian untuk Pembuktian Algoritma

Seperti yang dapat dilihat dari apa yang telah kita pelajari pada bagian sebelumnya, induksi matematika jelas sangat berguna untuk membuktikan kebenaran sebuah teorema atau fungsi yang melibatkan perhitungan bilangan bulat yang berulang. Tetapi apa guna induksi matematika untuk membuktikan kebenaran sebuah algoritma?

Sebuah algoritma kerap kali akan memiliki bagian yang melakukan perhitungan bilangan atau data secara berulang. Kita dapat menggunakan konsep perulangan pada pemrograman untuk menerapkan perhitungan bilangan ataupun data secara berulang. Misalnya, algoritma berikut menghitung hasil kali dari dua buah bilangan bulat:

defkali(m, n):

if m <0:

return-1# error

else:

        i =0

        result =0

while(m != i):

            result = result + n

            i = i +1

return result

yang secara matematis dapat dituliskan sebagai fungsi berikut:

f(m,n)=∑i=1nm;n≥0

atau lebih sederhananya:

m×n=m+m+m+...+m  dimana n kali

dan secara otomatis tentunya pernyataan matematis tersebut dapat kita buktikan dengan menggunakan induksi matematika. Pembuktian perulangan yang lebih kompleks sendiri dapat dilakukan dengan teknik yang dikenal dengan nama loop invariant.