INDUKSI MATEMATIKA

Prinsip Induksi Matematika Sebuah cara pembuktian yang sering dipakai, simple, dan sangat ampuh dalam matematika kombinatorial dan ilmu komp...

Prinsip Induksi Matematika

Sebuah cara pembuktian yang sering dipakai, simple, dan sangat ampuh dalam matematika kombinatorial dan ilmu komputer, dikenal dengan prinsip induksi matematika. Induksi matematika adalah metode pembuktian untuk proposisi bilangan bulat.

Untuk suatu pernyataan tertentu yang melibatkan sebuah bilangan asli n, jika kita dapat menunjukkan bahwa :

    Pernyataan itu benar untuk n = n₀, dan

    Pernyataan itu benar untuk n = k+1, dengan mengasumsikan bahwa pernyataan itu benar untuk n = k, (k ≥ n₀), 

maka kita dapat menyimpulkan bahwa pernyataan itu benar untuk semua bilangan asli n ≥ n₀.

Langkah (1) dinamakan basis induksi, sedangkan langkah (2) dinamakan langkah induksi. Di samping itu, asumsi bahwa pernyataan tersebut benar untuk n = k di dalam langkah (2) biasanya dinamakan hipotesis induksi.

Induksi Matematika pada Barisan Bilangan

Contoh 1 :

Buktikan bahwa  untuk semua n ≥1.

Solusi:

Misalkan P(n) menyatakan  untuk semua n ≥1.

1. Basis induksi.

Akan dibuktikan P(1) benar untuk n = 1.

Perhatikan bahwa:

Jadi, basis induksi benar.

2. Langkah induksi.

Misalkan P(k) benar, yaitu 

Akan dibuktikan P(k+1) juga benar yaitu 

Perhatikan bahwa:

Karena (1) dan (2) benar, maka terbukti bahwa  untuk semua n ≥1, juga benar.

Atau

step 1)  untuk n=1

                       =1(1+1)/2

=1 (benar)

step 2)  untuk n=k

1+2+3+...+k=k(k+1)/2 (benar)

step 3) akan dibuktikan bahwa n=k+1 juga benar

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

k ( k + 1 ) / 2 +(  k + 1) =  (k + 1)( k + 2) / 2

[ k ( k + 1 )  + 2(  k + 1)] /2 = ( k + 1)( k + 2) / 2  sifat distribusi (a +b)(c+d) = a (c + d) + b ( c + d)

(k + 1)( k + 2) / 2 =  ( k + 1)( k + 2) / 2  terbukti

Induksi Matematika pada Ketidaksamaan

Contoh 2:

Buktikan bahwa  untuk setiap bilangan bulat n ≥ 5.

Solusi:

Misalkan P(n) menyatakan  untuk setiap bilangan bulat n ≥ 5.

1.) Basis induksi.

Akan dibuktikan P(5) benar untuk n = 5.

Perhatikan bahwa:

Jadi, basis benar.

    2.) Langkah induksi.

Misalkan P(k) benar, yaitu 

Akan dibuktikan P(k+1) juga benar yaitu 

Perhatikan bahwa:

Karena (1) dan (2) benar, maka terbukti bahwa  untuk setiap bilangan bulat n ≥ 5,  juga benar.

Induksi Matematika pada Keterbagian

Contoh 3:

Buktikan bahwa  habis dibagi 3 untuk semua bilangan bulat n ≥ 1.

Solusi:

Misalkan P(n) menyatakan  habis dibagi 3 untuk semua bilangan bulat n ≥ 1.

Basis induksi.

Akan dibuktikan P(1) benar untuk n = 1.

Perhatikan bahwa: 

Jadi, basis benar.

Langkah induksi.

Misalkan P(k) benar, yaitu  habis dibagi 3

Akan dibuktikan P(k+1) juga benar yaitu  habis dibagi 3

Perhatikan bahwa:

Karena (1) dan (2) benar, maka terbukti bahwa  habis dibagi 3 untuk semua bilangan bulat n ≥ 1,

juga benar.

LATIHAN:

1. Gunakan prinsip induksi matematika untuk membuktikan pernyataan berikut adalah benar.
1. , untuk semua bilangan bulat n ≥ 1.
2. , untuk setiap bilangan bulat positif n.
3. habis dibagi 7 untuk semua bilangan bulat n ≥ 1.
4. , untuk semua bilangan bulat tak negatif n.
2. Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lainnya hanya sekali saja. Buktikan dengan induksi matematika bahwa jika ada n orang tamu maka jumlah jabat tangan yang terjadi adalah