Induksi Matematika

Kuntum Khaira Ummah

201731290

H

Induksi Matematika

A.   Pengertian

Induksi matematika adalah :

      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.

Contoh :

Jumlah bilangan bulat positif dari 1 sampai n adalah n(n+1)/2

Bukti :

Misalkan n = 6 à p(6) adalah “Jumlah bilangan bulat positif dari 1 sampai 6 adalah 6(6+1)/2” terlihat bahwa :

      1 + 2 + 3 + 4 + 5 + 6 = 21 è 6(7)/2 = 21

Sehingga proposisi (pernyataan) tersebut benar.

2. 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 :

p(n) benar

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

Digunakan untuk memperlihatkan bahwa pernyataan benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil.

Buat implikasi untuk fungsi berikutnya benar untuk setiap bilangan bulat positif.

Ø  Langkah induksi

Berisi asumsi (andaian) yang menyatakan bahwa p(n) benar.

Asumsi tersebut dinamakan hipotesis induksi.

Bila kedua langkah tersebut benar maka pembuktian bahwa p(n) benar untuk semua bilangan positif n.

Contoh :

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

Ø  Basis induksi

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

      1 = 1(1+1)/2

         = 1(2)/2

         = 2/2

         = 1

Ø  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

Ø  Basis induksi

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

1 = 1(1+1)/2

= 1(2)/2

= 2/2

= 1

Ø  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

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 :

p(n₀) benar

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 :

1). 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

Ø  Basis induksi

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

       2⁰ = 1 = 2⁰⁺¹ -1

       = 2¹ -1

      = 2 – 1

      = 1

Ø  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

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

      Langkah (i) dan (ii) dibuktikan benar, maka untuk semua bilangan bulat tidak negatif n, terbukti bahwa 2⁰+ 2¹+ 2²+…+ 2ⁿ= 2ⁿ⁺¹ -1 .

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

Ø  Basis induksi

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

Ø  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.