Induksi Matematika

INDUKSI MATEMATIKA

1.    PENGERTIAN INDUKSI MATEMATIKA

Induksi matematika atau disebut juga induksi lengkap sering dipergunakan untuk pernyataan-pernyataan yang menyangkut bilangan-bilangan asli. Atau dalam kata lain induksi matematika merupakan metode pembuktian untuk proposisi perihal bilangan bulat dan merupakan teknik pembuktian yang baku dalam matematika.
Pembuktian cara induksi matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua bilangan asli atau semua bilangan dalam himpunan bagiannya. Caranya ialah dengan menunjukkan bahwa sifat itu benar untuk n = 1 (atau S(1) adalah benar), kemudian ditunjukkan bahwa bila sifat itu benar untuk n = k (bila S(k) benar) menyebabkan sifat itu benar untuk n = k + 1 (atau S(k + 1) benar).

1+2+3+4+...+n = n(n+1) / 2

Contohnya:

1)      Apakah pernyataan tersebut benar ?
kita coba memasukkan n = 2 apakah hasilnya adalah 2 ?

2(2+1) / 3 = 2 ternyata benar

2)      Kita coba masukkan  n = 5

5(5+1) / 2 = 15 ternyata benar, 1+2+3+4+5 = 15

Dari contoh soal diatas terbukti bahwa kita tidak harus menggunakan cara yang terkesan panjang untuk membuktikan nilai dari suatu soal yang ingin ketahui.

2.     PROPOSISI PERIHAL BILANGAN BULAT

Proposisi merupakan istilah yang digunakan untuk kalimat pernyataan yang memiliki arti penuh dan utuh, atau dalam kata lain proposisi merupakan pernyataan mengenai hal-hal yang bernilai benar atau salah.

Proposisi yang menyangkut perihal bilangan bulat cukup banyak ditemui dalam matematiks diskret. Proposisi tersebut mengaitkan suatu masalah yang dihubungkan dengan bilangan bulat.

Dalam matematika banyak fenomena yang manyatakan bahawa p(n) benanr untuk semua bilangan bulat positif n. Dimana dalam hal ini p(n) disebut juga fungsi proposisi.

Contoh:

Misalkan p(n) adalah proposisi yang menyatakan : “jumlah bilangan bulat positif dari 1 sampai nadalah n(n+1)/2”. Buktikan bahwa p(n) benar!

Jawab:

Misalnya untuk n=5, p(5) adalah: : jumlah bilangan bulat positif dari 1 sampai 5 adalah 5(5+1)/2, terlihat bahwa:

1+2+3+4+5=15=5(6)/2.

Contoh 2 : Jika ingin menemukan rumus jumlah dari n buah bilangan ganjil positif yang pertama. Misalnya untuk n = 1, 2, 3, 4, 5, perhatikan jumlah n bilangan ganjil positif pertama

 n = 1 ® 1 = 1

 n = 2 ® 1 + 3 = 4

 n = 3 ® 1 + 3 + 5 = 9

 n = 4 ® 1 + 3 + 5 + 7 = 16

 n = 5 ® 1 + 3 + 5 + 7 + 9 = 25

Dari nilai-nilai penjumlahan, bahwa jumlah n buah bilangan ganjil yang pertama adalah n2

3.   Prinsip Induksi Sederhana

Misalkan p(n) adalah proposisi bilangan bulat positif dan ingin dibuktikan bahwa p(n) adalah benar untuk semua bilangan bulat positif n. Maka langkah-langkahnya adalah sebagai berikut :

a.       p(n) benar

b.       Jika p(n) benar, maka p(n+1) juga benar untuk setiap n ³ 1

Sehingga p(n) benar untuk semua bilangan bulat positif n.

  Basis Induksi dan Langkah Induksi

 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 kedua langkah tsb benar, maka sudah dibuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.

• Basis induksi digunakan untuk memperlihatkan bahwa pernyataan tersebut benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil. Langkah induksi harus memperlihatkan bahwa p(n) ® p(n+1) benar untuk semua bilangan bulat positif.

·  Contoh  : Tunjukkan bahwa untuk n ³ 1, 1+2+3+…+n = n(n+1)/2 melalui induksi matematika

Penyelesaian:

 (i) Basis induksi : p(1) benar, karena untuk n = 1 kita peroleh

 1 = 1(1+1)/2

    = 1(2)/2

    =2/2

    = 1

(ii) Langkah induksi : misal p(n) benar, yaitu mengasumsikan bahwa:

          1+2+3+...+n=n(n+1)/2

     Adalah benar, kita juga harus memperlihatkan bahwa

      p(n+1) juga benar, 1+2+3+…+n+(n+1) = (n+1) [(n+1) +1] /2.

Untuk membuktikan ini, tunjukkan bahwa:

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

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

                                     = [(n² +n)/2] + (n+1) [(n2 +n)/2] + [(2n+2)/2]

                                   = (n² + 3n + 2)/2

                                  =(n+1)(n+2)/2

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

Karena langkah (i) dan (ii) telah dibuktikan benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ³ 1, 1+2+3+…+n = n(n+1)/2:  sama.

4.   Prinsip Induksi yang Dirampatkan

è Prinsip induksi sederhana dapat dirampatkan (generalized).

Misalkan p(n) adalah pernyataan perihal bilangan bulat n ³ n₀. Untuk membuktikannya perlu menunjukkan bahwa :

a.       p(n₀) benar

b.       Jika p(n) benar, maka p(n+1) juga benar untuk setiap n ³ n₀

          sehingga p(n) benar untuk semua bilangan bulat n ³ n₀

·  Contoh  :

a)       Untuk semua bilangan bulat tidak negatif n, buktikan dengan induksi matematika bahwa 20+21+22+…+2n = 2n+1-1

           Penyelesaian:

            Misalkan p(n) adalah proposisi bahwa untuk semua bilangan bulat tidak negatif n,      

            20+21+22+…+2n = 2n+1-1.

(i)                  Basis induksi : p(0) benar, karena untuk n = 0 (bilangan bulat tidak negatif pertama), kita peroleh : 2⁰ = 1 = 2⁰⁺¹ – 1

                            = 2¹ – 1

                            =2 – 1

                            = 1

(ii)                Langkah induksi

Misalkan p(n) benar, yaitu proposisi :

        2⁰+ 2¹+ 2²+…+ 2ⁿ= 2ⁿ⁺¹ -1

Diasumsikan benar (hipotesis induksi). Perlihatkan bahwa p(n+1) juga benar, yaitu :

         2⁰+ 2¹+ 2²+…+ 2ⁿ+ 2ⁿ⁺¹ = 2^(n+1)+1 -1

Hal ini dapat ditunjukkan sebagai berikut :

                         2⁰+ 2¹+ 2²+…+ 2ⁿ+ 2ⁿ⁺¹ = (2⁰+ 2¹+ 2²+…+ 2ⁿ) + 2⁽ⁿ⁺¹⁾

                                                            = 2^(n+1)+1 -1 + 2ⁿ⁺¹  (dari hipotesis induksi)

                                        = (2ⁿ⁺¹ + 2ⁿ⁺¹) – 1

                                        = (2 . 2ⁿ⁺¹) – 1

                                        = 2ⁿ⁺² – 1

                                        = 2^(n+1)+1 -1

          Langkah (i) dan (ii) dibuktikan benar, maka untuk semua bilangan bulat tidak negatif  

           n, terbukti bahwa 2⁰+ 2¹+ 2²+…+ 2ⁿ= 2ⁿ⁺¹ -1 .

b)      Buktikan dengan induksi matematika bahwa 3ⁿ < n! untuk n bilangan bulat positif yang lebih besar dari 6

Penyelesain:

Misalkan p(n) adalah proposisi bahwa 3ⁿ < n! untuk n bilangan bulat positif yang lebih besar dari 6

(i)                  Basis induksi

              p(7) benar à 3⁷ < 7! « 2187 < 5040

(ii)                Langkah induksi

Misalkan bahwa p(n) benar, yaitu asumsikan bahwa 3ⁿ < n! adalah benar. Perlihatkan juga bahwa p(n+1) juga benar, yaitu 3ⁿ⁺¹ < (n+1)!

Hal ini dapat ditunjukkan sbb :

        3ⁿ⁺¹ < (n+1)!

        3 . 3ⁿ < (n+1) . n!

        3ⁿ . 3 / (n+1) < n!

Menurut hipotesis induksi, 3ⁿ < n!, sedangkan untuk n > 6, nilai 3/(n+1) < 1, sehingga 3/(n+1) akan memperkecil nilai di ruas kiri persamaan. Efek nettonya, 3ⁿ . 3/(n+1) < n! jelas benar.

Langkah (i) dan (ii) dibuktikan benar, maka terbukti bahwa 3ⁿ < n! untuk n bilangan bulat positif lebih besar dari 6.