Start by saying what the statement is that you want to prove: “Let \(P(n)\) be the statement…” To prove that \(P(n)\) is true for all \(n \ge 0\text{,}\) you must prove two facts:
Base case: Prove that \(P(0)\) is true. You do this directly. This is often easy.
Inductive case: Prove that \(P(k) \imp P(k+1)\) for all \(k \ge 0\text{.}\) That is, prove that for any \(k \ge 0\) if \(P(k)\) is true, then \(P(k+1)\) is true as well. This is the proof of an if … then … statement, so you can assume \(P(k)\) is true (\(P(k)\) is called the inductive hypothesis). You must then explain why \(P(k+1)\) is also true, given that assumption.