INDUKSI MATEMATIKA

 A.   DEVINISI INDUKSI MANUSIA

       Induksi matematika merupakan suatu metode pembuktian deduktif dalam matematika untuk menyatakan suatu pernyataan adalah benar untuk semua bilangan asli. Meski namanya induksi. Induksi matematika atau disebut juga induksi lengkap sering dipergunakan untuk pernyataan-pernyataan yang menyangkut bilangan-bilangan asli.

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

       Untuk membuktikan apakah pernyataan ini bernilai benar atau tidak untuk semua bilangan asli, ada dua langkah yang dilakukan, yaitu:

Jika benar, dan

Jika benar yang mengakibatkan juga benar,

Maka  bernilai benar untuk setiap bilangan asli n.

      Misalkan akan dibuktikan suatu pernyataan bahwa jumlah n bilangan asli pertama, yaitu 1+2+...+n, adalah sama dengan .

     Untuk membuktikan bahwa pernyataan itu berlaku untuk setiap bilangan asli, langkah- langkah yang dilakukan adalah sebagai berikut:

1.     Cara Biasa / Basis
                   Menunjukkan bahwa pernyataan tersebut benar untuk n = 1. Jelas sekali bahwa jumlah 1 bilangan asli pertama adalah = 1. Jadi pernyataan tersebut adalah benar untuk n = 1. Untuk n =1, Ruas kiri = 1 Sedangkan Ruas kanan =  1 Kerena ruas kiri = ruas kanan, maka persamaan benar untuk n=1.

2.     Menunjukkan bahwa jika pernyataan tersebut benar untuk n = k, maka pernyataan tersebut juga benar untuk n = k+1.

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

v CONTOH  1 :

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.

v CONTOH  2 :

Jumlah n buah bilangan ganjil positif pertama adalah n2.

Bukti :

Misalkan n = 6 buah (n = 1, 2, 3, 4, 5, 6) maka :

n = 1 à 1 = 1                               è (1)2 = 1

n = 2 à 1+3 = 4                          è (2)2 = 4

n = 3 à 1+3+5 = 9                      è (3)2 = 9
n = 4 à 1+3+5+7 = 16                è (4)2 = 16
n = 5 à 1+3+5+7+9 = 25            è (5)2 = 25
n = 6 à 1+3+5+7+9+11 = 36      è (6)2 = 36

Sehingga proposisi (pernyataan) tersebut adalah benar.

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

Ada dua langkah pembuktian yang digunakan dalam induksi yaitu

a)     Dengan Basis Induksi

b)    Dengan langkah Induksi

a)    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

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

v CONTOHNYA  :

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

Penyelesain :

a)    Menggunakan Basis induksi :

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

          1 = 1(1+1)/2

             = 1(2)/2

             = 2/2

             = 1

b)    Menggunakan 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

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

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

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

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

      = (n2+3n+2)/2

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

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

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

2.     Coba anda gunakan induksi matematika untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n2.

Penyelesain :

a)    Basis induksi

p(1) benar à jumlah 1 buah bilangan ganjil positif pertama adalah 12 = 1

b)    Langkah induksi

Misalkan p(n) benar maka à asumsi bahwa : 1+3+5+…+(2n-1) = n2

adalah benar (hipotesis induksi).

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

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

Hal ini dapat ditunjukkan sebagai berikut ini :

1+3+5+…+(2n-1)+(2n+1) = [1+3+5+…+(2n-1)]+(2n+1)

= n2 + (2n+1)

= n2 + 2n + 1

= (n+ 1)2

         Langkah (a) dan (b) dibuktikan benar, maka untuk jumlah n buah bilangan ganjil positif pertama adalah n2.      

C.   PRINSIP INDUKSI YANG DI RAMPATKAN

   Dalam prinsip induksi sederhana dapat juga dirampatkan atau di  sebut generalized.   Misalkan p(n) adalah pernyataan perihal yang bilangan bulat nya yaitu adalah n ³ n0.

Untuk membuktikannya perlu menunjukkan bahwa :

·        p(n0) benar

·        Jika p(n) benar, maka p(n+1) juga benar untuk setiap n ³ n0

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

v CONTOHNYA  :

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

Penyelesain : 

Misalkan p(n) adalah proposisi bahwa untuk semua bilangan bulat tidak negatif n, 20+ 21+ 22+…+ 2n= 2n+1 -1

a)    Basis induksi 

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

 20 = 1 = 20+1 -1

            = 21 -1

            = 2 – 1

            = 1

b)    Langkah induksi 

     Misalkan p(n) benar, yaitu proposisi : 20+ 21+ 22+…+ 2n= 2n+1 -1 Diasumsikan benar (hipotesis induksi). Perlihatkan bahwa p(n+1) juga benar, yaitu :

20+ 21+ 22+…+ 2n+ 2n+1 = 2(n+1)+1 -1

Hal ini dapat ditunjukkan sebagai berikut :

20+ 21+ 22+…+ 2n+ 2n+1 = (20+ 21+ 22+…+ 2n) + 2(n+1)

= 2(n+1)+1 -1 + 2n+1  (dari hipotesis induksi)

= (2n+1 + 2n+1) – 1

= (2 . 2n+1) – 1

= 2n+2 – 1

= 2(n+1)+1 -1

Langkah (a) dan (b) dibuktikan benar, maka untuk semua bilangan bulat tidak negatif n, terbukti bahwa 20+ 21+ 22+…+ 2n= 2n+1 -1

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

Penyelesain :

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

a)    Basis induksi

p(7) benar à 37 < 7! « 2187 < 5040

b)    Langkah induksi 

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

Hal ini dapat ditunjukkan sebagai berikut :

 3n+1 < (n+1)!

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

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

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

Langkah (a) dan (b) dibuktikan benar, maka terbukti bahwa 3n < n! untuk n bilangan bulat positif lebih besar dari 6