INDUKSI MATEMATIKA

INDUKSI MATEMATIKA 

1.1 Pengertian Induksi Matematika

Metode pembuktian untuk proposisi perihal bilangan bulat.

Induksi matematika merupakan teknik pembuktian yang baku di dalam matematika.Induksi matematika dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas

1.2 Prinsip Induksi Sederhana 

Misal p(n) adalah pernyataan yang bergantung pada n bilangan bulat positif. Kita ingin membuktikan bahwa p(n) benar utnuk semua bilangan bulat positif. Langkah induksi: 

1.    Basis Induksi: tunjukan p(1) benar 

2.    Hipotesa induksi: Misal p(n) benar untuk semua bilangan positif n ≥ 1. 

3.    Buktikan bahwa p(n+1) benar. 

Contoh :

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

i. Basis induksi

p(1) benar à n = 1 diperoleh dari :

     1 = 1(1+1)/2

        = 1(2)/2

        = 2/2

        = 1

ii. Langkah induksi

Misalkan p(n) benar à asumsi bahwa :

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

Adalah benar (hipotesis induksi).

Perlihatkan bahwa p(n+1) juga benar yaitu :

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

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

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

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

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

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

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

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

     Langkah (i) dan (ii) dibuktikan benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ³ 1, 1+2+3+…+n = n(n+1)/2

1.3 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 :

1.   p(n₀) benar

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

sehingga p(n) benar untuk semua bilangan bulat n ³ n_0.

Contoh :

Untuk semua bilangan bulat tidak negatif n, buktikan dengan induksi matematika bahwa 2⁰+ 2¹+ 2²+…+ 2ⁿ= 2ⁿ⁺¹ -1

Misalkan p(n) adalah proposisi bahwa untuk semua bilangan bulat tidak negatif n, 2⁰+ 2¹+ 2²+…+ 2ⁿ= 2ⁿ⁺¹ -1

i. Basis induksi

p(0) benar à untuk n = 0 (bilangan bulat tidak negatif pertama) diperoleh dari :

           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