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