Matematika diskrit bab Induksi matematika

Assalamu'alaikum Wr.Wb.

Pada kesempatan ini saya akan berbagi tentang induksi matematika. Induksi Matematika adalah cara standar dalam membuktikan bahwa sebuah pertanyaan tertentu berlaku untuk setiap bilangan asli. Pembuktian dengan cara ini terdiri dari dua langkah, yaitu:

- Menunjukan bahwa pernyataan itu berlaku untuk bilanagn 1.

- Menunjukan bahwa jika pernyataan itu berlaku untuk bilanagn n, maka pernyataan itu juga berlaku untuk bilangan n+1.

 Contoh 1 :

Gunakan induksi matematika (5 ^ n) -1 habis dibagi 4 untuk setiap n adalah bilangan positif dan n=k.+1

Jawab:

untuk n = bilangan positif misal 1 :

(5 ^ n)-1 habis dibagi 4 untuk n=1, (5 ^ 1) -1 = 5 -1= 4, habis dibagi 4

untuk n= k +1

(5 ^k+1) -1 =5.(5 ^ k)-1

                   = (1+4) . (5 ^ k)-1

                   = (5 ^k)+4.(5 ^ k)-1

                   =((5 ^ k)-1)+4.(5^k)

Berdasar asumsi , (5 ^ k)-1 habis dibagi4. Sedangkan 4.(5 ^ k) juga habis dibagi 4. Dengan demikian (5 ^ k+1)-1 habis dibagi 4. Karena langkah dasar dan langkah induktif terbukti, maka dapat disimpulkan bahwa 5^n-1 dapat dibagi 4 untuk setiap n=bilangan positif.

 NB: ^ artinya pangkat 

Contoh 2:

Buktikan 1+2+3+....+n= n(n+1) , dengan n adalah bilangan positif dan n=k+1

                                           2

Jawab:

n= bilangan positif maka,

jika n=1, ruas kiri 1=1 => ruas kanan 1(1+1)/2 = 1 ,hasil ruas kiri = ruas kanan.

       n=2, ruas kiri 1+2=3 => ruas kanan 2(2+1)/2= 3

       n = 3, ruas kiri 1+2+3= 6 => ruas kanan 3(3+1)/2= 6, dan seterusnya...

n= k+1
Induksi p(k) benar => p(k+1) benar, p(k) benar berarti:
1+2+3+....+n = n(n+1)/2, untuk posisi n diganti (k+1) sesuai permintaan soal.
1+2+3+....+k= k(k+1)/2
1+2+....+k+(k+1) = (k+1) ((k+1) +1)
                                         2
1+2+....+k+(k+1) = (1+2+...+k)+(k+1)
= k(k+1)/2 + (k+1)
= k(k+1) + 2 (k+1), disamakan penyebutnya 
                2
= k^2 + 3k + 2
             2
= (k+1) (k+2) ,  untuk angka 2 dipisah untuk mendapatkan (k+2) => (k+1)+1 (nilai tetap sama)

           2
= (k+1)((k+1)+1) ,
             2
Karena kembali ke posisi awal maka ini membuktikan bahwa:
1+ 2+ 3+....+n= n (n+1)/2, untuk n >= 1

contoh 3:
Buktikan 1+3+5+....+(2n-1)=n^2

Secara basis:

n=1, ruas kiri 1 => ruas kanan 1^2 = 1
n= 2, ruas kiri 1+ 3= 4 => ruas kanan 2^2 = 4
n= 3, ruas kiri 1+3+5 = 9 => ruas kanan 3^2 = 9
Karena ruas kiri dan ruas kanan sama nilainya maka pernyataan di atas terbukti.

Secara induksi:
1+2+3+...+(2n-1)= n^2, maka jika n= k+1 hasilnya:
1+2+3+...+(2n-1)+ (2(k+1)-1) = (k+1)^2

Latihan:
1. Buktikan dengan induksi matematika bahwa n^5 - n habis dibagi 5 untuk n bilangan positif!
2. Buktikan 3^n < n! untuk n bilangan bulat positif lebih besar dari 6.

Jawab:

1. )
Secara basis :
n=2 , 2^5 -2 = 30 habis dibagi 5, terbukti

Secara induksi n=k+1
(k+1)^5 - (k+1) = k^5 + 1^5 - (k+1)
                          = k^5 + 1 - k + 1
                          = k^5 - k, intinya hasil akhir kembali ke bentuk n^5 - n maka terbukti

2.) 
Secara basis:
n=7, n lebih besar dari 6
3^n < n!
3 ^7 < 7!
2187 < 5040, terbukti

Secara induksi n=k+1
3^n < n!
3^ (k+1) < (k+1) !

Sekian yang dapat saya sampaikan kurang lebihnya mohon ma'af , ini sarana untuk belajar bersama.
Wassalamu'alaikum Wr.Wb

Artikel menarik tentang :
Tes TPA potensi bilangan dan pembahasanya
Tes TPA aritmatika dan pembahasanya
Kumpulan kata - kata mutiara