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.

**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.

## 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.