PRINSIP INDUKSI KUAT
Misal p(n) adalah suatu pernyataan yang menyangkut bilangan bulat. Kita akan buktikan
bahwa
p(n) adalah benar utnuk semua bilangan bulat n≥n0. Langkah induksi:
1.
Basis Induksi: p(n0) benar.
2.
Hipotesa Induksi : Andaikan utnuk semua bilangn bulat n≥n0, p(n0), p(n0 + 1), .
. . ,
p(n)
benar.
Contoh:
Tunjukan bahwa bilangan bulat positif adalah bilangan prima jika hanya jika hanya habis dibagi 1 dan dirinya sendiri.
Jawab:
Kita
akan buktikan bahwa utnuk setiap bilangan bulat n≥2, dapat dinyatakan sebagai
hasil
kali satu atau lebih bilangan prima.
•
Basis Induksi
Untuk
n = 2 ⇒ 2 = 1.2 ( 2 dapat dinyatakan sebagai perkalian satu
bilangan prima)
benar.
•
Hipotesa induksi
Misalkan
2,3,4, . . ., n dapat dinyatakan sebagai hasil kali satu atau lebih bilangan
prima.
•
Akan dibuktikan bahwa (n+1) dapat dinyatakan sebagai hasil kali satu atau lebih
bilangan
prima.
Bukti:
Jika
(n+1) adalah bilangan prima , maka (n+1) dapat dinyatakan sebagai hasil kali
satu
bilangan prima yaitu (n+1) = 1.(n+1)
Jika
(n+1) bukan bilangan prima, maka terdapat bilangan positif a sedemikian
sehingga
2< a < (n+1) yang membagi habis (n+1). Dengan kata lain:
Dari
hipotesa, karena 2< a,b<n maka a dan b dapat dinyatakan sebagai hasil
kali
satu
atau lebih bilangan prima. Jadi, ab juga dapat dinyatakan sebagai hasil kali
satu
atau
lebih bilangan prima, sehingga (n+1) dapat dinyatakan sebagai hasil kali satu
Tidak ada komentar:
Posting Komentar