3.6: Mathematical Induction  The Strong Form
 Page ID
 8396
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
You may have heard of Fibonacci numbers. They occur frequently in mathematics and life sciences. They have even been applied to study the stock market! Fibonacci numbers form a sequence every term of which, except the first two, is the sum of the previous two numbers. Mathematically, if we denote the \(n\)th Fibonacci number \(F_n\), then \[F_n = F_{n1} + F_{n2}. \label{eqn:FiboRecur}\] This is called the recurrence relation for \(F_n\).
Some students have trouble using (3.6.1): we are not adding \(n1\) and \(n2\). The subscripts only indicate the locations within the Fibonacci sequence. Hence, \(F_1\) means the first Fibonacci number, \(F_2\) the second Fibonacci number, and so forth. Compare this to dropping ten numbers into ten boxes, and each box is labeled with the numbers 1 through 10. Let us use \(a_i\) to denote the value in the \(i\)th box. When we say \(a_7\), we do not mean the number 7. Instead, we mean the number stored in Box 7. Expressed in words, the recurrence relation (3.6.1) tells us that the \(n\)th Fibonacci number is the sum of the \((n1)\)th and the \((n2)\)th Fibonacci numbers. This is easy to remember: we add the last two Fibonacci numbers to get the next Fibonacci number.
The recurrence relation implies that we need to start with two initial values. We often start with \(F_0=0\) (image \(F_0\) as the zeroth Fibonacci number, the number stored in Box 0) and \(F_1=1\). We combine the recurrence relation for \(F_n\) and its initial values together in one definition:
\[F_0=0, \quad F_1=1, \qquad
F_n = F_{n1} + F_{n2}, \quad\mbox{for } n\geq2\]
We have to specify that the recurrence relation is valid only when \(n\geq2\), because this is the smallest value of \(n\) for which we can use the recurrence relation. What happens if you want to find \(F_1\) using this formula? You will get \(F_1=F_0+F_{1}\), but \(F_{1}\) is undefined!
The sum of the zeroth and the first Fibonacci numbers give us the second Fibonacci number: \[F_2 = F_1 + F_0 = 1 + 0 = 1.\] Continuing in this fashion, we find \[ \begin{array}{lclclcl} F_3 &=& F_2+F_1 &=& 1+1 &=& 2, \\ F_4 &=& F_3+F_2 &=& 2+1 &=& 3, \\ F_5 &=& F_4+F_3 &=& 3+2 &=& 5, \\ F_6 &=& F_5+F_4 &=& 5+3 &=& 8, \\ \hfil\vdots&& \hfil\vdots && \hfil\vdots && \vdots \end{array}\] Following this pattern, what are the values of \(F_7\) and \(F_8\)?
Fibonacci numbers enjoy many interesting properties, and there are numerous results concerning Fibonacci numbers. As a starter, consider the property \[F_n < 2^n, \qquad n\geq1.\] How would we prove it by induction?
Since we want to prove that the inequality holds for all \(n\geq1\), we should check the case of \(n=1\) in the basis step. When \(n=1\), we have \(F_1=1\) which is, of course, less than \(2^1=2\). In the inductive hypothesis, we assume that the inequality holds when \(n=k\) for some integer \(k\geq1\); that is, we assume \[F_k < 2^k\] for some integer \(k\geq1\). Next, we want to prove that the inequality still holds when \(n=k+1\). So we need to prove that \[F_{k+1} < 2^{k+1}.\]
To make use of the inductive hypothesis, we need to apply the recurrence relation of Fibonacci numbers. It tells us that \(F_{k+1}\) is the sum of the previous two Fibonacci numbers; that is, \[F_{k+1} = F_k + F_{k1}.\] The only thing we know from the inductive hypothesis is \(F_k < 2^k\). So, as it stands, it does not tell us much about \(F_{k+1}\).
A remedy is to assume in the inductive hypothesis that the inequality also holds when \(n=k1\); that is, we also assume that \[F_{k1} < 2^{k1}.\] Therefore, unlike all the problems we have seen thus far, the inductive step in this problem relies on the last two \(n\)values instead of just one. In terms of dominoes, imagine they are so heavy that we need the combined weight of two dominoes to knock down the next. Then \[F_{k+1} = F_k + F_{k1} < 2^k + 2^{k1} = 2^{k1}(2+1) < 2^{k1} \cdot 2^2 = 2^{k+1},\] which will complete the induction. This modified induction is known as the strong form of mathematical induction. In contrast, we call the ordinary mathematical induction the weak form of induction.
The proof still has a minor glitch! To be able to use the inductive hypothesis in the recurrence relation \[F_{k+1} = F_k + F_{k1},\] both subscripts \(k\) and \(k1\) must be at least 1, because the statement claims that \(F_n < 2^n\) for all \(n\geq1\). This means we need \(k\geq2\). Consequently, in the basis step, we have to assume the inequality holds for at least the first two values of \(n\).
In terms of the domino effect, the chain reaction of the falling dominoes starts at \(k=2\). We have to make sure that the first two dominoes will fall, so that their combined weight will knock down the third domino. Then the combined weight of the second and the third dominoes will knock over the fourth domino. The chain reaction will carry on indefinitely.
Symbolically, the ordinary mathematical induction relies on the implication \(P(k) \Rightarrow P(k+1)\). Sometimes, \(P(k)\) alone is not enough to prove \(P(k+1)\). In the case of proving \(F_n < 2^n\), we actually use \[[P(k1) \wedge P(k)] \Rightarrow P(k+1).\] We need to assume in the inductive hypothesis that the result is true when \(n=k1\) and \(n=k\).
More generally, in the strong form of mathematical induction, we can use as many previous cases as we like to prove \(P(k+1)\).
Strong Form of Mathematical Induction. To show that \(P(n)\) is true for all \(n \geq n_0\), follow these steps:
Verify that \(P(n)\) is true for some small values of \(n\geq n_0\).
Assume that \(P(n)\) is true for \(n=n_0,n_0+1,\ldots,k\) for some integer \(k\geq n^*\).
Show that \(P(k+1)\) is also true.
The idea behind the inductive step is to show that \[[\,P(n_0)\wedge P(n_0+1)\wedge\cdots\wedge P(k1)\wedge P(k)\,] \Rightarrow P(k+1).\] We may not need to use all of \(P(n_0),P(n_0+1),\ldots,P(k1),P(k)\). In fact, we may only need the last few of them, for example, \(P(k3),P(k2),P(k1)\) and \(P(k)\). The number of previous cases required to establish \(P(k+1)\) tells us how many initial cases we have to verify in the basis step. We do not know how many we need until the inductive step. For this reason, it is wise to start with a draft.
Example \(\PageIndex{1}\label{eg:induct301}\)
Show that \(F_n<2^n\) for all \(n\geq1\).
Remark
We have already worked on the draft in the discussion above. We know that we need to verify the first two \(n\)values in the basis step, and to assume that the inequality holds for at least two cases.
 Answer

Proceed by induction on \(n\). When \(n=1\) and \(n=2\), we find \[\displaylines{ F_1 = 1 < 2 = 2^1, \cr F_2 = 1 < 4 = 2^2. \cr}\] Therefore, the inequality holds when \(n=1, 2\). Assume it holds for \(n=1,2,\ldots,k\), where \(k\geq2\). In particular, we have \[F_k < 2^k, \qquad\mbox{and}\qquad F_{k1} < 2^{k1},\] where \(k\geq2\). Then \[F_{k+1} = F_k + F_{k1} < 2^k + 2^{k1} = 2^{k1} (2+1) < 2^{k1}\cdot 2^2 = 2^{k+1}.\] Hence, the inequality still holds when \(n=k+1\), which completes the induction.
Recurrence relation can be used to define a sequence. For example, if the sequence \(\{a_n\}_{n=1}^\infty\) is defined recursively by \[a_n = 3 a_{n1}  2 \qquad \mbox{for } n\geq2,\] with \(a_1=4\), then \[\displaylines{ a_2 = 3a_1  2 = 3\cdot42 = 10, \cr a_3 = 3a_2  2 = 3\cdot102 = 28. \cr}\] Identity involving such sequences can often be proved by means of induction.
Example \(\PageIndex{2}\label{eg:induct302}\)
The sequence \(\{b_n\}_{n=1}^\infty\) is defined as \[b_1 = 5, \quad b_2 = 13, \qquad b_n = 5b_{n1}  6b_{n2} \quad\mbox{for } n\geq3.\] Prove that \(b_n = 2^n+3^n\) for all \(n\geq1\).
 Answer

Proceed by induction on \(n\). When \(n=1\), the proposed formula for \(b_n\) says \(b_1=2+3=5\), which agrees with the initial value \(b_1=5\). When \(n=2\), the proposed formula claims \(b_2=4+9=13\), which again agrees with the definition \(b_2=13\). Assume the formula is valid for \(n=1,2,\ldots,k\) for some integer \(k\geq2\). In particular, assume \[b_k = 2^k+3^k, \qquad\mbox{and}\qquad b_{k1} = 2^{k1}+3^{k1}.\] We want to show that the formula still works when \(n=k+1\). In other words, we want to show that \[b_{k+1} = 2^{k+1}+3^{k+1}.\] Using the recurrence relation and the inductive hypothesis, we find \[\begin{aligned} b_{k+1} &=& 5b_k  6b_{k1} \\ &=& 5(2^k+3^k)6(2^{k1}+3^{k1}) \\ &=& 5\cdot2^k+5\cdot3^k6\cdot2^{k1}6\cdot3^{k1} \\ &=& 5\cdot2^k+5\cdot3^k2\cdot3\cdot2^{k1}2\cdot3\cdot3^{k1} \\ &=& 5\cdot2^k+5\cdot3^k3\cdot2^k2\cdot3^k \\ &=& 2\cdot2^k+3\cdot3^k \\ &=& 2^{k+1}+3^{k+1} \end{aligned}\] which is what we want to establish. This completes the induction, and hence, the claim that \(b_n = 2^n+3^n\).
handson exercise \(\PageIndex{1}\label{he:induct301}\)
The sequence \(\{c_n\}_{n=1}^\infty\) is defined as \[c_1 = 7, \quad b_2 = 29, \qquad c_n = 5b_{n1}  6b_{n2} \quad\mbox{for } n\geq3.\] Prove that \(c_n = 5\cdot3^n4\cdot2^n\) for all integers \(n\geq1\).
Example \(\PageIndex{3}\label{eg:induct303}\)
Show that all integers \(n\geq24\) can be expressed as \(4x+9y\) for some integers \(x,y\geq0\).
Definition
The expression \(4x+9y\) is called a linear combination of 4 and 9, and \(x\) and \(y\) are called the coefficients of the linear combination.
Remark
We want to prove that any sufficiently large integer \(n\) can be written as a linear combination of 4 and 9 with nonnegative coefficients. This problem is called the postage stamp problem for the obvious reason: can we use only 4cent and 9cent stamps to obtain an \(n\)cent postage for all integers \(n\geq24\)? Not too surprisingly, it is also called the money changing problem (imagine replacing stamps with coins).
Remark
The spirit behind mathematical induction (both weak and strong forms) is making use of what we know about a smaller size problem. In the weak form, we use the result from \(n=k\) to establish the result for \(n=k+1\). In the strong form, we use some of the results from \(n=k,k1,k2,\ldots\,\) to establish the result for \(n=k+1\).
 Discussion

Let us first look at the inductive step, in which we want to show that we can write \(k+1\) as a linear combination of 4 and 9. The key step of any induction proof is to relate the case of \(n=k+1\) to a problem with a smaller size (hence, with a smaller value in \(n\)).
Imagine you want to send a letter that requires a \((k+1)\)cent postage, and you can use only 4cent and 9cent stamps. You could first put down a 4cent stamp. Then you still need to come up with the remaining postage of \((k+1)4=k3\) cents. If you could use 4cent and 9cent stamps to make up the remaining \((k3)\)cent postage, the problem is solved. Therefore, in the inductive hypothesis, we need to assume that it can be done when \(n=k3\).
For the whole argument to work, \(k3\) has to be within the range of the \(n\)values that we consider. So we need \(k3\geq24\); that is, we want \(k\geq27\). Consequently, we have to verify the claim for \(n=24,25,26,27\) in the basis step.
 Solution

Proceed by induction on \(n\). We find \[\begin{aligned} 24 &=& 4\cdot6 + 9\cdot0, \\ 25 &=& 4\cdot4 + 9\cdot1, \\ 26 &=& 4\cdot2 + 9\cdot2, \\ 27 &=& 4\cdot0 + 9\cdot3. \end{aligned}\] Hence, the claim is true when \(n=24,25,26,27\). Assume it is true when \(n=24,25,\ldots,k\) for some integer \(k\geq27\). In particular, since \(k3\geq24\), this assumption assures that \[k3 = 4x+9y\] for some nonnegative integers \(x\) and \(y\). It follows that \[\begin{aligned} k+1 &=& 4+(k3) \\ &=& 4+4x+9y \\ &=& 4(1+x)+9y, \end{aligned}\] where \(1+x\) and \(y\) are nonnegative integers. This shows that the claim is still true when \(n=k+1\), thereby completing the induction.
handson Exercise \(\PageIndex{2}\label{he:induct302}\)
Show that all integers \(n\geq2\) can be expressed as \(2x+3y\) for some nonnegative integers \(x\) and \(y\).
Summary and Review
 If, in the inductive step, we need to use more than one previous instance of the statement that we are proving, we may use the strong form of the induction.
 In such an event, we have to modify the inductive hypothesis to include more cases in the assumption.
 We also need to verify more cases in the basis step.
 Finally, we need to rewrite the whole proof to make it coherent.
Exercise \(\PageIndex{1}\label{ex:induct301}\)
Use mathematical induction to prove the identity \[F_1^2+F_2^2+F_3^2+\cdots+F_n^2 = F_n F_{n+1}\] for any integer \(n\geq1\).
Exercise \(\PageIndex{2}\label{ex:induct302}\)
Use induction to prove the following identity for all integers \(n\geq1\): \[F_1+F_3+F_5+\cdots+F_{2n1} = F_{2n}.\]
Exercise \(\PageIndex{3}\label{ex:induct303}\)
Use induction to prove that \[\frac{F_1}{F_2F_3} + \frac{F_2}{F_3F_4} + \frac{F_3}{F_4F_5} + \cdots + \frac{F_{n2}}{F_{n1}F_n} = 1  \frac{1}{F_n}\] for all integers \(n\geq3\).
Exercise \(\PageIndex{4}\label{ex:induct304}\)
Use induction to prove that any integer \(n\geq8\) can be written as a linear combination of 3 and 5 with nonnegative coefficients.
Exercise \(\PageIndex{5}\label{ex:induct305}\)
A football team may score a field goal for 3 points or^{1} a touchdown (with conversion) for 7 points. Prove that, for any integer \(n\geq12\), it is possible for a football team to score \(n\) points with field goals and touchdowns.
Exercise \(\PageIndex{6}\label{ex:induct306}\)
An island country only issues 1cent, 5cent and 9cent coins. Due to shortage in copper, all 1cent coins were recalled. Prove that, using just 5cent and 9cent coins, one can pay an \(n\)cent purchase for any \(n\geq32\).
Exercise \(\PageIndex{7}\label{ex:induct307}\)
The sequence \(\{b_n\}_{n=1}^\infty\) is defined recursively by \[b_n = 3 b_{n1}  2 \qquad \mbox{for } n\geq2,\] with \(b_1=4\). Use induction to prove that \(b_n=3^n+1\) for all \(n\geq1\).
Exercise \(\PageIndex{8}\label{ex:induct308}\)
The sequence \(\{c_n\}_{n=1}^\infty\) is defined recursively as \[c_1=3, \quad c_2=9, \qquad c_n = 7c_{n1}  10c_{n2}, \quad\mbox{for } n\geq3.\] Use induction to show that \(c_n = 4\cdot2^n5^n\) for all integers \(n\geq1\).
Exercise \(\PageIndex{9}\label{ex:induct309}\)
The sequence \(\{d_n\}_{n=1}^\infty\) is defined recursively as \[d_1=2, \quad d_2=56, \qquad d_n = d_{n1} + 6d_{n2}, \quad\mbox{for } n\geq3.\] Use induction to show that \(d_n = 5(2)^n+4\cdot3^n\) for all integers \(n\geq1\).
Exercise \(\PageIndex{10}\label{ex:induct310}\)
The sequence \(\{a_n\}_{n=1}^\infty\) is defined recursively as \[a_1=2, \quad a_2=4, \qquad a_n = 2a_{n1} + 3a_{n2}, \quad\mbox{for } n\geq3.\] Use induction to show that \(a_n > \left(\frac{5}{2}\right)^n\) for any integer \(n\geq4\).

Although it is possible for a team to score 2 points for a safety or 8 points for a touchdown with a twopoint conversion, we would not consider these possibilities in this simplified version of a real football game.↩