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.

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