The Strong Form of Induction (with Examples)

by Dave
(DAVE)—

You’re trying to prove a statement is true using mathematical induction, but then you realize that the induction hypothesis doesn’t seem strong enough. What do you do? It turns out that there is more than one way to do induction. Let’s learn what strong induction is.

This video explains what the strong form of induction is and how it differs from mathematical induction, as discussed before. I also work through three examples to help you understand how it works.

The Statement of the Strong Form of Induction

Compare the following two statements.

Mathematical Induction. If $P$ is a subset of the positive integers with the following properties: $0 \in P$, and for all $k\in \mathbb{N}$, $k \in P$ implies $k+1 \in P$, then $P$ is the set of positive integers.

Strong Induction. If $P$ is a subset of the positive integers with the following properties: $0 \in P$, and for all $k\in \mathbb{N}$, $0,1,\ldots , k \in P$ implies $k+1 \in P$, then $P$ is the set of positive integers.

Notice in the second statement (the strong form of induction), the induction hypothesis is different. By assuming more, by assuming $0,1,\ldots , k \in P$ instead of just $k \in P$ a proof may become less clustered and streamlined. To illustrate how this works we will explore the Lucas numbers.

Lucas numbers

Numbers in the sequence $1, 3, 4, 7, 11, 18, \ldots$ are called Lucas numbers. They are defined inductively by, $L_1=1$, $L_2=3$, $L_n=L_{n-1}+L_{n-2}$ for all $n\geq 3.$

Example 1. Prove that for all positive integers $n$, \begin{equation}\label{lucasnum}L_n < \left(\frac{7}{4}\right)^n.\end{equation}

Solution. For the basis step notice that $$ L_1=1< \left(\frac{7}{4}\right)^1=\frac{7}{4}. $$ For a strong induction hypothesis, we assume that $\eqref{lucasnum}$ holds true for $n=1, \dots, k-1.$ Then we find, \begin{align*} L_k =L_{k-1}+L_{k-2} & < \left(\frac{7}{4}\right)^{k-1}+\left(\frac{7}{4}\right)^{k-2} \\ & =\left(\frac{7}{4}\right)^{k-2} \left(\frac{7}{4}+1\right) \\ & =\left(\frac{7}{4}\right)^{k-2} \left(\frac{11}{4}\right) \\ & < \left(\frac{7}{4}\right)^{k-2} \left(\frac{7}{4}\right)^{2} \\& =\left(\frac{7}{4}\right)^{k}. \end{align*} Because the inequality is true for $n=k$ whenever it is true for the integers $1, 2, \dots, k-1$, we conclude, by the Strong Form of Induction that, $L_n < (7/4)^n$ for all $n\geq 1.$

More Examples of Strong Induction

Here are two more examples to have fun with.

Example 2. Show that any amount of postage more than one-cent can be formed just using two-cent and three-cent stamps.

Proving a statement about postage stamps using strong induction
Proving a statement about postage stamps using strong induction

Example 3. Define a function recursively for all positive integers $n$ by $f(1)=1$, $f(2)=5$, and for $n>2$, $f(n+1)=f(n)+2f(n-1).$ Show that $f(n)=2^n+(-1)^n$, using strong induction.

Using strong induction to prove a formula concerning a recursively defined function
Using strong induction to prove a formula concerning a recursively defined function

Conclusion

There you go, three examples using strong induction. In the following video, we will work on some more examples by doing some exercises. In a later video, I will prove that the well-ordering axiom, mathematical induction, and the strong form of induction are equivalent.

To learn a great deal more on this topic, consider taking the online course The Natural Numbers.