Induction Proof Structure.

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:

1. Base case: Prove that \(P(0)\) is true. You do this directly. This is often easy.

2. 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.

Assuming you are successful on both parts above, you can conclude, “Therefore by the principle of mathematical induction, the statement \(P(n)\) is true for all \(n \ge 0\text{.}\)”