Strong induction is similar to proof by induction except that to prove the inductive step, one may need to use all of the proceeding statements that have already been proven.

A proof by strong induction is a proof using the following strategy:

• Base case: Prove \(P(1), P(2), \dots, P(n)\) for some number \(n.\)
• Inductive step: Prove \(P(1) \wedge P(2) \wedge \dots \wedge P(i) \rightarrow P(i+1)\) for \(i \geq 1.\) In the proof of the inductive step, \(P(1) \wedge P(2) \wedge \dots \wedge P(i)\) are called the inductive hypotheses.

Example

Claim: Let \(a_1, a_2, a_3, \dots\) be defined by \begin{align} & a_1 = 1 \\ & a_2 = 1 \\ & a_3 = 1 \\ & a_i = a_{i-1}+a_{i-2}+a_{i-3} \text{ for } i \geq 4 \end{align} Prove that \(a_i\) is odd for every \(i.\)

Proof: This proof is using strong induction.

Base cases: The base cases are \(a_1,\) \(a_2\) and \(a_3,\) which are all odd.
Inductive step: Let \(n \geq 3\) and assume \(a_1, a_2, \dots, a_n\) are odd. The goal is to show \(a_{n+1}\) is odd. Since \(a_n, a_{n-1},\) and \(a_{n-2}\) are odd, there exist integers \(u,\) \(v\) and \(w\) such that \begin{align} a_{n} & = 2u+1 \\ a_{n-1} & = 2v+1 \\ a_{n-2} & = 2w+1 \end{align} Therefore, \begin{align} a_{n+1} & = a_n + a_{n-1} + a_{n-2} \\ & = (2u+1)+(2v+1)+(2w+1) \\ & = 2(u+v+w+1)+1 \end{align} Therefore, \(a_{n+1}\) is odd, which completes the proof.