Strong induction

Strong induction

Axiom of Induction: For all \(n\in \mathbb{N}\), Let \(P(n)\) be a statement. If \(P(1)\) is true and, for all \(n\in\mathbb{N}\), \(P(n)\implies P(n+1)\), then \(P(n)\) is true for all \(n\in\mathbb{N}\).

Strong induction changes the hypothesis slightly.

Strong Induction: For all \(n\in\mathbb{N}\), let \(P(n)\) be a statement. If \(P(1)\) is true and, for all \(n\), the statement \[ P(1)\wedge P(2)\wedge\cdots\wedge P(n)\implies P(n+1) \] is true, then \(P(n)\) is true for all \(n\in\mathbb{N}\).

This means that if you prove \(P(1)\) true, and then, by assuming all of the preceeding statements \(P(1),P(2),\ldots, P(n)\) true you can prove \(P(n+1)\) true, then all \(P(n)\) are true.

Example. (See page 187).

Proposition: Any score of \(12\) or higher is possible in a football game where the scores are either field goals (\(3\) points) or touchdowns (\(7\) points). Notice that \(11\) is not a possible score, so \(12\) is the smallest score such that all larger scores are possible.

Example: \(12\) is possible as \(4\times 3\) field goals; \(13\) is possible as \(2\times 3\) field goals plus a \(7\) point touchdown; \(14\) is possible as two touchdowns; and so on.

Proof: Suppose that \(P(n)\) is the statement that ‘\(n\) is a possible score.’ We know that \(P(12)\), \(P(13)\), and \(P(14)\) are true.

Our strong induction hypothesis is this:

Suppose that \(P(12), P(13), P(14),\ldots, P(n)\) are all true and \(n\ge 15\). We want to show that this implies that \(P(n+1)\) is true.

Since all \(P(n)\) up to \(n\) are true, \(P(n-2)\) is true by the inductive hypothesis, and so \(n-2\) is a possible score. But then \(n+1=(n-2)+3\) is also possible, because it’s obtained by however you get \(n-2\), plus a field goal.

This establishes the proof by strong induction.

Notice that the key step was that we had to “go back” more than one step to find what we needed.

Strong induction cont’d

Why does strong induction hold? It holds because it can be changed into regular induction.

Suppose \(P(n)\) is a sequence of statements that satisfy the conditions of strong induction, so \(P(1)\) is true and \(P(n+1)\) is a consequence of all of the preceeding statements \(P(1),\ldots,P(n)\).

Let \(S(1)=P(1)\), and let \(S(n)=P(1)\wedge P(2)\cdots\wedge P(n)\). We apply regular induction to the set of statements \(S(n)\).

  • So \(S(n)\) is a sequence of statements, and \(S(1)\) is true.
  • Also, we know that \(S(n)\implies P(n+1)\) by our hypothesis.
  • But \(S(n)\wedge P(n+1)=S(n+1)\), and since \(S(n)\) is true and \(P(n+1)\) is true, so is \(S(n+1)\).
  • Therefore we’ve shown that \(S(1)\) is true and \(S(n)\implies S(n+1)\) for all \(n\in\mathbb{N}\).
  • By regular induction, \(S(n)\) is true for all \(n\).
  • But the only way \(S(n)\) is true is if all \(P(j)\) for \(1\le j\le n\) are true.
  • So all \(P(n)\) are also true.