strong induction

Strong induction is equivalent to an induction proof, except there are multiple base cases that we build the inductive step upon. There is no need to use strong induction except for convenience, as simple induction can prove everything that strong induction can.

Difference between strong induction and regular induction

The primary difference between strong induction proof and a normal proof by induction is that in the induction hypothesis we must assume that $P(n)$ holds for multiple values of $n$, from $n_0$ all the way up to any $n\ge n_k$ where $n_k$ is the largest base case; whereas in induction proofs we only need to assume one arbitrary but fixed value for which $P(n)$ holds.

A strong induction looks similar to an inductive proof except we need multiple legs to climb the ladder…

• Predicate: Same as induction proof
• Induction Variable: Same as induction proof
• Base Case: Show that $P(n)$ holds for multiple base cases $n_0,\dots ,n_k$.
• Induction Hypothesis: Let $n$ be any arbitrary value greater than or equal to $n_k$. Assume that $P(n)$ holds for any arbitrary $m$ such that $n_0\le m\le n$. As in an inductive proof, we can omit this step for brevity.
• Induction Step: Same as regular induction, except we can refer to all cases from $n_0$ to $n_k$.