Strong Induction Proof Structure.

Again, start by saying what you want to prove: “Let \(P(n)\) be the statement…” Then establish two facts:

  1. Base case: Prove that \(P(0)\) is true.

  2. Inductive case: Assume \(P(k)\) is true for all \(k \lt n\text{.}\) Prove that \(P(n)\) is true.

Conclude, “therefore, by strong induction, \(P(n)\) is true for all \(n \gt 0\text{.}\)

in-context