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.