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.