The Strong Form of Induction (with Examples)

(D4M) — Here is the video transcript for this video.

In this article, you’ll learn about the strong form of induction. We’ll learn what it is and work through some samples. Let’s go.

Strong Induction

The principle of strong induction is also a method of proof and is frequently useful in the theory of numbers.  This principle can also be used to prove statements about arrays, sequences, and many other structures. Familiarity with this type of argument is essential to subsequent work.

Theorem. (Principle of Strong Induction) A set of positive integers that contains the integer 1, and that has the property: for every positive integer $n,$ if the set contains $1,2,\ldots,n,$ then it also contains the integer $n+1$; must be the set of all positive integers.

Proof. Let $P$ be the set with the stated property and let $S$ be the set consisting of all positive integers not in $P.$ Assuming that $S$ is nonempty, we can choose $n$ to be the least integer in $S.$ Then $n>1$ and so none of the integers $1,2,3,\ldots,n-1$ lies in $S.$ Then by the second property, $n=(n-1)+1$ is in $P,$ which contradicts the definition of $S.$ Thus, $S$ is empty and $P$ must be the set of all positive integers. $\blacksquare$

While the hypothesis is “stronger”, both statements are actually logically equivalent to each other, as the next theorem states.

Theorem. (Induction Principles) The following statements are logically equivalent.

(Mathematical Induction) If $P$ is a subset of the positive integers with the following properties:

1. $0 \in P$, and
2. 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:

1. $0 \in P$, and
2. for all $k\in \mathbb{N}$, $0,1,…, k \in P$ implies $k+1 \in P$,

then $P$ is the set of positive integers.

Which one you choose is often a matter of convenience. Some statements are much easier to work with using one or the other.

Example. Use the principle of induction to establish that for all $n\geq 1$

$a^n-1=(a-1)\left(a^{n-1}+a^{n-2}+a^{n-3}+\text{…}+a+1\right).$

Solution. For $n=1,$ $a-1=a-1$ is obvious. Suppose that the equation is true for $k$ namely,

$\left(a^k-1\right)=(a-1)\left(a^{k-1}+a^{k-2}+a^{k-3}+\text{…}+a+1\right).$

Then for $k+1$ we have

\begin{align*}  \left(a^{k+1}-1\right) & =\left(a^{k+1}-a^k+a^k-1\right) \\ & =a^k(a-1)+(a-1)\left(a^{k-1}+a^{k-2}+a^{k-3}+\cdots+a+1\right) \end{align*}

and so

$\left(a^{k+1}-1\right)=(a-1)\left(a^k+a^{k-1}+a^{k-2}+a^{k-3}+\text{…}+a+1\right).$

We can also rely on the strong principle of induction, by considering the formula:

$$a^{n+1}-1 = (a+1)\left(a^n-1\right)-a\left(a^{n-1}-1\right).$$

$\blacksquare$

Now in order to understand the difference between strong induction and mathematical induction, we will consider some examples of Lucas numbers.

These examples, illustrate when strong induction might be the preferred method.

Lucas Numbers

To illustrate the strong form of induction we will discuss the 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, \qquad L_2=3, \qquad L_n=L_{n-1}+L_{n-2} \quad \text{for all n\geq 3}.$$

The Lucas numbers have a number of interesting mathematical properties, and they can be used to generate a variety of different patterns and sequences.

They also show up in a surprising number of real-world applications, from financial markets to computer algorithms.

Example. Prove that for all positive integers $n$,

$$\label{lussevenfour} L_n < \left(\frac{7}{4}\right)^n.$$

Solution. For the basis step notice that

$$L_1=1< \left(\frac{7}{4}\right)^1=\frac{7}{4}.$$

Now assume (strong induction hypothesis) that \cref{lussevenfour} 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}  \\[5pt] & =\left(\frac{7}{4}\right)^{k-2} \left(\frac{7}{4}+1\right) \\[5pt] & =\left(\frac{7}{4}\right)^{k-2} \left(\frac{11}{4}\right) \\[5pt] & < \left(\frac{7}{4}\right)^{k-2} \left(\frac{7}{4}\right)^{2}  \\[5pt] & = \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  Strong Induction, that $L_n < (7/4)^n$ for all $n\geq 1$. $\blacksquare$

More Examples Using Strong Induction

When first studying mathematical induction a student often runs into solving the postage stamp problem.

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

Solution. Notice that 2-cent and 3-cent stamps can be formed using 2-cent and 3-cent stamps, so the base case is obvious.  Let $k$ be a positive integer with $k\geq 1$.  For an induction hypothesis (strong), assume that any amount of postage up to $k$-cents can be formed using 2-cent and 3-cent stamps.  Then using $k+1 = k-1+ 2$, and the fact that $2$ is a 2-cent stamp and $k-1$ can be formed using 2-cent and 3-cent stamps, we see that $k+1$ can be formed using 2-cent and 3-cent stamps. Hence by strong induction, any amount can be formed using 2-cent and 3-cent stamps. $\blacksquare$

For our next example, let’s use a new function.

Define a function recursively, for all positive integers $n$ by

$$f(1)=1, \quad f(2)=5, \quad f(n+1)=f(n)+2f(n-1).$$

For example, $f(1)=1$, $f(2)=5$, $f(3)=7$, $f(4)=17$, and so on.

We can (exhaustively) search for patterns until we find this gem:

Example. Prove that $f(n)=2^n+(-1)^n$ for all positive integers $n$.

Solution. For $n=1$ and $n=2$, we have $f(1)=1=2^1+(-1)^1$ and $f(2)=5=2^2+(-1)^2$, so the base case holds.  Let $k$ be a positive integer with $k\geq 1$.  Assume $f(n)=2^n+(-1)^n$ holds for $n=0,.\ldots, k$.  Then

\begin{align} f(k+1) & = f(k)+2f(k-1) \\ & = 2^k+(-1)^k +2 ( 2^{k-1}+(-1)^{k-1}) \\ &  = 2^k +2^k +(-1)^k + 2((-1)^{k-1}) \\ &  = 2^{k+1} + (-1)^{k+1} \end{align}

Therefore, the result follows by strong induction. $\blacksquare$

Conclusion

We’ve looked at two different types of inductive reasoning- the weak form and the strong form. Each has its own benefits and drawbacks in terms of proof. The weak form is the weakest type of induction because it relies on a mere coincidence between two events. The strong form is stronger than the weak form because it requires that there be a logical connection between the premises and the conclusion. In practice, these forms of induction are often used together to create a powerful argument.

Here is a series of 9 articles that guide you through learning mathematical induction. You’ll learn that mathematical induction is a proof technique used to establish a statement for all positive integers. These articles highlight how this proof technique is helpful in solving problems, and provide several examples to illustrate its use.

Also, don’t forget to check the video series on mathematical induction on YouTube.