Contoh 4.6.3.
Buktikan bahwa setiap bilangan asli yang lebih besar dari 1 merupakan bilangan prima atau dapat ditulis sebagai hasil kali bilangan-bilangan prima.
Penyelesaian.
Pertama, gagasannya: Jika kita mengambil suatu bilangan \(n\text{,}\) mungkin bilangan itu prima. Jika demikian, kita selesai. Jika tidak, bilangan itu komposit, sehingga merupakan hasil kali dua bilangan yang lebih kecil. Masing-masing faktor ini lebih kecil daripada \(n\) (tetapi setidaknya 2), sehingga kita dapat mengulangi argumen tersebut untuk kedua bilangan itu. Kita telah mereduksi masalah menjadi kasus yang lebih kecil.
Sekarang pembuktian formalnya:
Bukti.
Misalkan \(P(n)\) adalah pernyataan, “\(n\) merupakan bilangan prima atau dapat ditulis sebagai hasil kali bilangan-bilangan prima.” Kita akan membuktikan bahwa \(P(n)\) benar untuk semua \(n \ge 2\text{.}\)
Kasus dasar: \(P(2)\) benar karena \(2\) memang bilangan prima.
Langkah induksi: Asumsikan \(P(j)\) benar untuk semua \(j \le k\text{.}\) Kita ingin menunjukkan bahwa \(P(k+1)\) benar. Artinya, kita ingin menunjukkan bahwa \(k+1\) merupakan bilangan prima atau merupakan hasil kali bilangan-bilangan prima. Jika \(k+1\) prima, kita selesai. Jika tidak, \(k+1\) memiliki lebih dari 2 pembagi, sehingga kita dapat menulis \(k+1 = m_1 \cdot m_2\text{,}\) dengan \(m_1\) dan \(m_2\) lebih kecil daripada \(k+1\) (dan lebih besar dari 1). Berdasarkan hipotesis induksi, \(m_1\) dan \(m_2\) masing-masing merupakan bilangan prima atau dapat ditulis sebagai hasil kali bilangan-bilangan prima. Dalam kedua hal tersebut, kita memperoleh bahwa \(m_1\cdot m_2 = k+1\) dapat ditulis sebagai hasil kali bilangan-bilangan prima.
Jadi, berdasarkan induksi kuat, \(P(n)\) benar untuk semua \(n \ge 2\text{.}\)