2.5b Strong Induction

Strong Induction

Strong induction extends simple induction by using an induction induction hypothesis which makes the stronger assumption that $P(0),P(1),\dots ,P(k)$ are all true.

Understanding

Between re or less powerful than the other. Recall that we mentioned that in simple induction, if the $k$-th domino falls, so does the $(k+1)$-th. In strong induction, if dominoes $1$ through $k$ fall, so does the $(k+1)$-th.

However, strong induction can greatly help out in certain cases.

Examples

Prove that for every $n\in \mathbb{N}$ where $n\ge 12$, there exist $x,y\in \mathbb{N}$ such that $n=4x+5y$

We proceed by weak induction on $n$ first. We must start with a few base cases:

• $n=12$: $12=4\cdot 3+5\cdot 0$
• $n=13$: $13=4\cdot 2+5\cdot 1$
• $n=14$: $14=4\cdot 1+5\cdot 2$
• $n=15$: $15=4\cdot 0+5\cdot 3$.

Since the theorem holds for the first 4 cases, we may proceed by with the inductive step by assuming our hypothesis; that $k=4x+5y$ holds for any $k\ge 15$:
$n=k+1=4x+5y+1=4(x-1)+5(y+1).$
As such, $k+1=4x^{\prime }+5y^{\prime }$ where $x^{\prime }=x-1$ and $y^{\prime }=y+1$.

We can also utilize strong induction for our inductive hypothesis. Assume that for some $k\ge 15$, the statement $n=4x+5y$ holds for all $n$ such that $12\le n\le k$. How will we show that the statement holds for $n=k+1$? Since $k\ge 15$, we know that $k+1\ge 16$ and $(k+1)-4\ge 12$. By the inductive hypothesis, there exist some $x^{\prime },y^{\prime }\in \mathbb{N}$ for which
$(k+1)-4=4x^{\prime }+5y^{\prime }.$
We see that for the values of

Prove that for every $n\in \mathbb{N}$ such that $n>1$ can be written as a product of one or more primes

We proceed by induction on $n$:

• Base case ($n=2$): $2$ is a prime number so the base case holds.
• Hypothesis: Assume that the statement holds for naturals $n$ up to $k$, such that $2\le n\le k$.
• Step: We must prove that either $k+1$ is either a prime number, or can be written as a product of primes:
  1. Since $k+1$ is prime, it is a product of itself, and we’re done.
  2. If $k+1$ is not prime, it can be written as $k+1=a\cdot b$ for some naturals $0<a,b\le k+1$, which are assumed by the inductive hypothesis to be able to be written as a product of primes. This is because any composite number has at least 3 factors (some perfect squares such as 4).

As such, we have proved using strong induction that the theorem holds.