INDUKSI

INDUKSI

                    I.      Pengertian induksi

Induksi matematika merupakan salah satu metode/cara pembuktian yang absah dalam  matematik untuk membuktikan suatu  pernyataan matematika apakah benar atau salah. Seringkali kita hanya menerima saja pernyataan atau argumen matematika, tanpa mengetahui kebenaran pernyataan tersebut. Oleh karena itu kita membutuhkan suatu metode untuk membuktikan kebenaran pernyataan matematika yang disebut induksi matematika.

Meskipun namanya induksi matematik, namun metode ini merupakan penalaran deduktif. Induksi matematik merupakan salah satu argumentasi pembuktian suatu teorema atau pernyataan matematika yang semesta pembicaranya kumpulan bilangan bulat atau lebih khusus himpunan bilangan asli. Melalui induksi matematik ini kita dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas.

                  II.      Tahapan Induksi Matematika

Induksi matematika adalah suatu metode yang digunakan untuk memeriksa validasi suatu pernyataan yang diberikan dalam himpunan bilangan positif atau himpunan bilangan asli. Pembuktian dengan cara ini terdiri dari tiga langkah, yaitu:

a.       Langkah Basis

       Menunjukkan bahwa pernyataan itu berlaku untuk bilangan 1

b.      Langkah Induksi

Menunjukkan bahwa jika pernyataan itu berlaku untuk bilangan n = k, maka pernyataan itu juga berlaku untuk bilangan n = k + 1

c.       Kesimpulan

               III.      Prinsip Induksi Matematika

Misalkan S adalah himpunan bagian N yang memiliki 2 sifat:
(1) S memiliki anggota bilangan 1; dan
(2) Untuk setiap k anggota N, jika k anggota S, maka k + 1 anggota S.
Maka diperoleh S = N.

Sebelum membuktikan prinsip induksi matematika di atas secara formal, kita akan mencoba memahaminya dengan menggunakan efek domino seperti berikut.

 

Pada gambar (a) di atas kita melihat sebaris 4 domino pertama yang ditata rapi dengan jarak antara masing-masing domino yang berdekatan kurang dari tinggi domino. Sehingga, jika kita mendorong domino nomor k ke kanan, maka domino tersebut akan merebahkan domino nomor (k + 1).

Proses ini ditunjukkan oleh gambar (b). Kita tentu akan berpikir bahwa apabila proses ini berlanjut, maka domino nomor (k + 1) tersebut juga akan merebahkan domino di sebelah kanannya, yaitu domino nomor (k + 2), dan seterusnya.

 Bagian (c) menggambarkan bahwa dorongan terhadap domino pertama merupakan analogi dari bilangan 1 menjadi anggota himpunan S. Hal ini merupakan langkah dasar dari proses efek domino. Selanjutnya, jika k anggota Sakan menyebabkan (k + 1) anggota S, akan memberikan langkah induktif dan melanjutkan proses perebahan domino. Sehingga, pada akhirnya kita akan melihat bahwa semua domino akan rebah. Atau dengan kata lain, domino yang memiliki nomor urut semua bilangan asli akan rebah. Hal ini merupakan analogi dari S = N. 

                 IV.      Prinsip Induksi Matematika (versi kedua)

Misalkan n₀ anggota N dan misalkan P(n) merupakan pernyataan untuk setiap bilangan asli n ≥ n₀. Apabila:

(1) Pernyataan P(n₀) benar;
(2) Untuk setiap k ≥ n₀, jika P(k) benar mengakibatkan P(k + 1) benar.

Maka P(n) benar untuk semua n ≥ n₀.

Berikut ini adalah beberapa contoh yang menunjukkan bagaimana Induksi Matematika dapat digunakan untuk membuktikan pernyataan tentang bilangan asli.

CONTOH

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

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

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

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