Selasa, 09 Oktober 2012

INDUKSI Matematika Diskrit



INDUKSI 

Induksi Matematika itu a/ cara atau sebagai pembuktian sebuah pernyataan tertentu,  diberlakukan untuk bilangan asli. Pembuktiannya terdiri dari 2 cara seperti,

Menunjukkan jika pernyataan itu berlaku u/ bilangan 1.
Menunjukkan kalau pernyataan itu diberlakukan u/ bilangan n, maka pernyataan untuk itu berlaku juga u/ bilangan n + 1.

Prinsip Induksi yang Sederhana

Induksi Matematika ini bisa kita artikan seperti ini
Misal u/ setiap bilangan Real N kita memiliki pernyataan P(n) yg hasilnya bisa benar (true) atau salah (false).

Misal>>

P(1)  kita nyatakan sebagai true (benar).
Jika P(n) adalah true (benar), maka P(n + 1) hasilnya juga true (benar)

jadinya P(n) true (benar) u/ setiap bilangan Real (asli) n.
Langkah pertama kita sebut sebagai Langkah Dasar, sedangkan Langkah kedua kita sebut sebagai Langkah Induktif.

Contoh 1
menggunakana induksi matematika u/ mengetes/ mengetahui jikalau jumlah n adalah bilangan ganjil, bilangan + positih pertama a/ n2.

Mari kita buktikan:

1.  Basis induksi: U/ n = 1, jumlah 1  bilangan ganjil positif pertama a/ 19 = 1. Hasilnya menjadi true (benar) krn jumlah 1 bilangan ganjil positif pertama a/ 1.

cara induksi:
jikalau p(n) adalah true (benar), seperti
1 + 3 + 5 + … + (2n – 1) = n2

a/ true (benar )>>>(hipotes dari induksi)
[perlu digaris bawahi jika bilangan ganjil positif ke-n a/ (
2n – 1)]

Kita juga harus membuktikan jika p(n +1) hasilnya adalah true (benar) seperti,

1 + 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)2
A/ benar. Hal ini dapat kita buktikan spt dibawah ini:

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

Krn langkah basis & langkah induksi ke2 telah diketahui jika hasilnya true (benar) jadi jumlah n bilangan ganjil positif pertama a/ n2.

Prinsip Induksi yang Dirapatkan/dipadatkan.

Misal p(n) a/ pernyataan tentang bilangan bulat & kita ingin mengetahui lebih lanjut jika  p(n) hasilnya true (benar) u/ all bilangan bulat  n3 n0. U/ membuktikan,kita hanya perlu tahu jika:

p(n0)  hasilnya true (benar), & u/semua bilangan bulat  n3 n0,

jika p(n) dinyatakan true (benar) maka p(n+1) juga hasilnya true  (benar)

Contoh>>

U/ all bil bulat bukan-negatif n, kita buktikan dengan induksi matematik jika

30 + 31 + 32 + … + 2n = 2n+1 – 1

Cara menyelesaikan:

1>Basis induksi.

u/ n = 0 (bukanlah bil bulat  neg pertama), we have:
30 = 30+1 – 1
Ini jelas benar, sebab  
30 = 1  
= 30+1 – 1
= 31 – 1
= 3– 1
= 1

2>Langkah induksi.

jikalau u/ semua bilangan bulat Bukanlah-negatif  n,
30 + 31 + 32 + … + 2n = 2n+1 – 1 
Kita nyatakan benar (hipotes induksi). Kita harus membuktikan bila,

30 + 31 + 32 + … + 2n + 2n+1 = 2(n+1) + 1 – 1

Hasilnya sama benar atau true. Kita buktikan sebagai berikut:

30 + 31 + 32 + … + 2n + 2n+1 = (30 + 31 + 32 + … + 2n) + 2n+1
= (2n+1 – 1) + 2n+1 (a/ H induksi)
= (2n+1 + 2n+1) – 1
= (2 . 2n+1) – 1
= 2n+2 – 1
= 2(n+1) + 1 – 1

Krn langkah pertama dan keduanya menyatakan hasilnya true (benar), jadi u/ semua bil bulat bukanlah-negatif n, karena telah kita buktikan jika
 30 + 31 + 32 + … + 2n = 2n+1 – 1