Page 6 - TUGAS UAS MD_NURUL HUDA_212110026

P(n) benar karena 2 dapat dituliskan sebagai bilangan prima.
Langkah Induktif

Ambil sebarang k bilangan bulat yang lebih besar dari 1. Asumsikan P(j)
benar untuk semua bilangan bulat j, dimana 1< j ≤ k. Harus dibuktikan P(k

+ 1) benar.

Pembuktian dibagi menjadi dua kasus.
- Jika (k + 1) bilangan prima, maka jelas (k + 1) pasti benar

- Jika (k + 1) bukan bilangan prima, maka (k + 1) dapat dinyatakan (k +
1) = a x b, dengan a dan b bilangan bulat sehingga 2 ≤ a ≤ b < k + 1.

Karena 2 ≤ a ≤ b < k + 1 berdasarkan asumsi a dan b merupakan
bilangan prima atau hasil kali bilangan prima. Maka (k + 1)

merupakan hasil kali bilangan prima.

Diperoleh, P(k + 1) benar :
Jadi, berdasarkan langkah basis dan langkah induktif maka P(n) benar

untuk semua bilangan bulat positif n yang lebih besar dari satu.

4. Latihan Soal :
Gunakan prinsip induksi kuat untuk membuktikan bahwa untuk
menyelesaikan suatu puzzle dengan n potongan diperlukan n – 1 langkah :

Bukti :
misal p(n) : untuk menyelesaikan suatu puzzle dengan n diperlukan n – 1

langkah

Langkah Basis :
Untuk puzzle dengan 1 potongan tidak diperlukan langkah untuk

menyelesaikan jadi p(1) benar.
Langkah Induksi :

Andaikan p(1), p(2), p(3), ..., p(n) benar (Hipotetis induksi).
Artinya untuk menyelesaikan puzzle dengan potongan

diperlukan n – 1 langkah. Akan ditunjukkan bahwa puzzle dengan n + 1

potongan memerlukan n langkah untuk menyelesaikan.
Bagi n + 1 potongan menjadi dua bagian yaitu dan sehinggah :

n + 1 = +

3