Page 6 - SINTA ANDRIYANI UAS MATEMATIKA DISKRIT

Adalah benar (hipotesis induksi). Kita harus menunjukkan bahwa p(n+1) juga
benar , yaitu:
1
2
0

2 + 2 + 2 +. . . . +2 + 2 +1 = 2 ( +1)+1 − 1
Juga benar. Ini kita tunjukkan sebagai berikut:
0
2
1

2 + 2 + 2 +. . . . +2 + 2 +1 = 2 ( +1)+1 − 1
2 +1 − 1 + 2 +1 = 2 +2 − 1
(2 +1 + 2 +1 ) − 1 = 2 +2 − 1
1
(2 . 2 +1 ) − 1 = 2 +2 − 1
2 +2 − 1 = 2 +2 − 1
• Karena Langkah 1 dan 2 telah di perolehkan benar, maka untuk semua
bilangan bulat tidak negative n, terbukti bahwa
2
0
1

2 + 2 + 2 +. . . . +2 = 2 +1 − 1

Contoh 2
Buktikan bahwa pernyataan di bawah ini benar untuk n bilangan asli!
3 + 9 + 13 … . +(4 − 1) = 2 +
2
Jawab
a. Basis induksi
n = 1, p = 1
(4 − 1) = 2 +
2
(4(1) − 1) = 2(1) + 1
2
4 – 1 = 2 + 1
3 = 3 benar
Karena untuk n = 1 benar maka Langkah pertama benar.
b. Andaikan p(n) benar
3 + 9 + 13 … . +(4 − 1) = 2 +
2
Maka akan di buktikan p(n+1) juga benar
3 + 9 + 13 … . +(4 − 1) + (4( + 1) − 1) = 2( + 1) + ( + 1)
2
Jadi
2
2
2 + + 4 + 4 − 1 = 2( + 2 + 1) + ( + 1)
2
2
2 + 5n + 3 = 2 + 4 + 2 + + 1
2 + 5n + 3 = 2 + 5n + 3
2
2
Karena untuk p(n) benar, di peroleh p(n+1) benar maka Langkah kedua benar
Jadi kesimpulannya karena Langkah a dan b benar maka terbukti

3