# Strong Induction

The Strong Principle of Mathematical induction

To prove that a predicate $P(n)$ holds for every number $n\geq n_0$,

Base Case. Prove $P(m)$ for all $m$ such that $n_0\leq m\leq n_1$.

Induction Hypothesis. Let $n\geq n_1$ be arbitrary but fixed, and assume that $P(m)$ holds whenever $n_0\leq m\leq n$.

Induction Step. Assuming the induction hypothesis, show that $P(n+1)$ holds.

Example. Consider the sequence $a_1=3$, $a_2=5$, and for all $n>2$, $a_n=3a_{n-1}-2a_{n-2}$. Prove by strong induction that $a_n=2^n+1$ for all integers $n\geq 1$.

Proof. Let $P(n)$ be the predicate $a_n=2^n+1$.

Base Case. \begin{align*}P(1): a_1=3=2^1+1\\P(2): a_2=5=2^2+1\end{align*}

Induction Hypothesis. Fix $n\geq 2$, and assume that for all $1\leq n\leq n$, $P(m)$ holds i.e. $a_m=2^m+1$.

Induction Step. Show $P(n+1)$ i.e. $a_{n+1}=2^{n+1}+1$ holds. \begin{align*}a_{n+1}&=3a_n-2a_{n-1}\\&=3(2^n+1)-2(2^{n-1}+1)\\&=2\cdot 2^n+1\\&=2^{n+1}+1\end{align*}

Well-Ordering Principle

Any nonempty set of nonnegative integers has a smallest element.

Well-Ordering Principle may appear to be unrelated to the Principle of Mathematical Induction, however the two are indeed equivalent to each other.

We now prove, with the aid of Well-Ordering Principle, the Fundamental Theorem of Arithmetic (every integer $n$ greater than 1 has a unique prime decomposition)

Proof. We prove by induction on $n$.

Base Case. $n_0=2=2^1$. We are done.

Induction Hypothesis. Fix $n\geq 2$, and suppose that we know that every $m$, $2\leq m\leq n$, has a unique prime decomposition (factorization).

Induction Step. We prove that the statement is true for $n+1$. If $n+1$ is a prime, we are done. Suppose that $n+1$ is not a prime. Let $S$ be the set of all its factors greater than 1. By Well-Ordering Principle, $S$ has the smallest element $p$, which must be prime. (otherwise $p$ wouldn’t be the smallest factor of $n+1$.) Let $q=\frac{n+1}{p}$. Then by induction hypothesis ($q\leq n$), $q$ has the unique prime decomposition $$q=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\ (p_1<p_2<\cdots<p_k)$$ Now $p$ is either $p_1$ or a smaller prime than $p_1$. If $p=p_1$ then $$n+1=p_1^{e_1+1}p_2^{e_2}\cdots p_k^{e_k}$$ If $p$ is a smaller prime than $p_1$, say $p_0$, then $$n+1=p_0^1p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$ It’s easy to show that no number can have more than one prime decomposition. This is left as an exercise for readers.

References.

 Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019