Struktur Pembuktian dengan Induksi.

Mulailah dengan menyatakan pernyataan yang ingin Anda buktikan: “Misalkan \(P(n)\) adalah pernyataan….” Untuk membuktikan bahwa \(P(n)\) benar untuk semua \(n \ge 0\text{,}\) Anda harus membuktikan dua fakta:
  1. Kasus dasar: Buktikan bahwa \(P(0)\) benar. Lakukan ini secara langsung. Bagian ini sering kali mudah.
  2. Langkah induksi: Buktikan bahwa \(P(k) \imp P(k+1)\) untuk semua \(k \ge 0\text{.}\) Artinya, buktikan bahwa untuk setiap \(k \ge 0\text{,}\) jika \(P(k)\) benar, maka \(P(k+1)\) juga benar. Ini adalah pembuktian pernyataan jika … maka …, sehingga Anda boleh mengasumsikan bahwa \(P(k)\) benar (\(P(k)\) disebut hipotesis induksi). Selanjutnya Anda harus menjelaskan mengapa \(P(k+1)\) juga benar berdasarkan asumsi tersebut.
Jika Anda berhasil membuktikan kedua bagian di atas, Anda dapat menyimpulkan, “Oleh karena itu, berdasarkan prinsip induksi matematika, pernyataan \(P(n)\) benar untuk semua \(n \ge 0\text{.}\)”
dalam konteks