- Last updated
- Save as PDF
- Page ID
- 7055
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vectorC}[1]{\textbf{#1}}\)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}}\)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}\)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)
Preview Activity \(\PageIndex{1}\): Exploring Statements of the Form \((\forall n \in \mathbb{N})(P(n))\)
One of the most fundamental sets in mathematics is the set of natural numbers \(\mathbb{N}\). In this section, we will learn a new proof technique, called mathematical induction, that is often used to prove statements of the form \((\forall n \in \mathbb{N})(P(n))\). In Section 4.2, we will learn how to extend this method to statements of the form \((\forall n \in T) (P(n))\), where \(T\) is a certain type of subset of the integers \(\mathbb{Z}\).
For each natural number \(n\), let \(P(n)\) be the following open sentence:
4 divides \((5^n - 1)\).
- Does this open sentence become a true statement when \(n = 1\)? That is, is 1 in the truth set of \(P(n)\)?
- Does this open sentence become a true statement when \(n = 2\)? That is, is 2 in the truth set of \(P(n)\)?
- Choose at least four more natural numbers and determine whether the open sentence is true or false for each of your choices.
All of the examples that were used should provide evidence that the following proposition is true:
For each natural number \(n\), 4 divides \((5^n - 1)\).
We should keep in mind that no matter how many examples we try, we cannot prove this proposition with a list of examples because we can never check if 4 divides \((5^n - 1)\) for every natural number \(n\). Mathematical induction will provide a method for proving this proposition.
For another example, for each natural number \(n\), we now let \(Q(n)\) be the following open sentence:
\[1^2 + 2^2 + ... + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}.\]
The expression on the left side of the previous equation is the sum of the squares of the first \(n\) natural numbers. So when \(n = 1\), the left side of equation (4.1.1) is \(1^2\). When \(n = 2\), the left side of equation (4.1.1) is \(1^2 + 2^2\).
- Does \(Q(n)\) become a true statement when
\(\bullet\ n = 1\)? (Is 1 in the truth set of \(Q(n)\)?
\(\bullet\ n = 2\)? (Is 1 in the truth set of \(Q(n)\)?
\(\bullet\ n = 3\)? (Is 1 in the truth set of \(Q(n)\)? - Choose at least four more natural numbers and determine whether the open sentence is true or false for each of your choices. A table with the columns \(n\), \(1^2 + 2^2 + ... + n^2\), and \(\dfrac{n(n + 1)(2n + 1)}{6}\) may help you organize your work.
All of the examples we have explored, should indicate the following proposition is true:
For each natural number \(n\), \(1^2 + 2^2 + ... + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}.\]
In this section, we will learn how to use mathematical induction to prove this statement.
Preview Activity \(\PageIndex{1}\): A Property of the Natural Numbers
Intuitively, the natural numbers begin with the number 1, and then there is 2, then 3, then 4, and so on. Does this process of “starting with 1” and “adding 1 repeatedly” result in all the natural numbers? We will use the concept of an inductive set to explore this idea in this activity.
Definition
A set \(T\) that is a subset of \(\mathbb{Z}\) is an inductive set provided that for each integer \(k\), if \(k \in T\), then \(k + 1 \in T\).
- Carefully explain what it means to say that a subset \(T\) of the integers \(\mathbb{Z}\) is not an inductive set. This description should use an existential quantifier.
- Use the definition of an inductive set to determine which of the following sets are inductive sets and which are not. Do not worry about formal proofs, but if a set is not inductive, be sure to provide a specific counterexample that proves it is not inductive.
(a) \(A = \{1, 2, 3, ..., 20\}\)
(b) The set of natural numbers, \(\mathbb{N}\)
(c) \(B = \{n \in \mathbb{N} | n \ge 5\}\)
(d) \(S = \{n \in \mathbb{Z} | n \ge -3\}\)
(e) \(R = \{n \in \mathbb{Z} | n \le 100\}\)
(f) The set of integers, \(\mathbb{Z}\)
(g) The set of odd natural numbers. - This part will explore one of the underlying mathematical ideas for a proof by induction. Assume that \(T \subseteq \mathbb{N}\) and assume that \(1 \in T\) and that \(T\) is an inductive set. Use the definition of an inductive set to answer each of the following:
(a) Is \(2 \in T\)? Explain.
(b) Is \(3 \in T\)? Explain.
(c) Is \(4 \in T\)? Explain.
(d) Is \(100 \in T\)? Explain.
(e) Do you think that \(T = \mathbb{N}\)? Explain.
Inductive Sets
The two open sentences in Preview Activity \(\PageIndex{1}\) appeared to be true for all values of \(n\) in the set of natural numbers, \(\mathbb{N}\). That is, the examples in this preview activity provided evidence that the following two statements are true.
- For each natural number \(n\), 4 divides \((5^n - 1)\).
- For each natural number \(n\), \(1^2 + 2^2 + ... + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}.\)
One way of proving statements of this form uses the concept of an inductive set introduced in Preview Activity \(\PageIndex{2}\). The idea is to prove that if one natural number makes the open sentence true, then the next one also makes the open sentence true. This is how we handle the phrase “and so on” when dealing with the natural numbers. In Preview Activity \(\PageIndex{2}\), we saw that the number systems \(\mathbb{N}\) and \(\mathbb{Z}\) and other sets are inductive. What we are trying to do is somehow distinguish \(\mathbb{N}\) from the other inductive sets. The way to do this was suggested in Part (3) of Preview Activity \(\PageIndex{2}\). Although we will not prove it, the following statement should seem true.
Statement 1: For each subset \(T\) of \(\mathbb{N}\), if \(1 \in T\) and \(T\) is inductive, then \(T = \mathbb{N}\).
Notice that the integers, \(\mathbb{Z}\), and the set \(S = \{n \in \mathbb{Z} | n \ge - 3\}\) both contain 1 and both are inductive, but they both contain numbers other than natural numbers. For example, the following statement is false:
Statement 2: For each subset \(T\) of \(\mathbb{Z}\), if \(1 \in T\) and \(T\) is inductive, then \(T = \mathbb{Z}\).
The set \(S = \{n \in \mathbb{Z} | n \ge - 3\} = \{-3, -2, -1, 0, 1, 2, 3, ...\}\) is a counterexample that shows that this statement is false.
Progress Check 4.1 (Inductive Sets)
Suppose that T is an inductive subset of the integers. Which of the following statements are true, which are false, and for which ones is it not possible to tell?
- \(1 \in T\) and \(5 \in T\).
- If \(1 \in T\), then \(5 \in T\).
- If \(5 \notin T\), then \(2 \notin T\).
- For each integer \(k\), if \(k \in T\), then \(k + 7 \in T\).
- For each integer \(k\), \(k \notin T\) or \(k + 1 \in T\).
- There exists an integer \(k\) such that \(k \in T\) and \(k + 1 \notin T\).
- For each integer \(k\), if \(k + 1 \in T\), then \(k \in T\).
- For each integer \(k\), if \(k + 1 \notin T\), then \(k \notin T\).
- Answer
-
Add texts here. Do not delete this text first.
The Principle of Mathematical Induction
Although we proved that Statement (2) is false, in this text, we will not prove that Statement (1) is true. One reason for this is that we really do not have a formal definition of the natural numbers. However, we should be convinced that Statement (1) is true. We resolve this by making Statement (1) an axiom for the natural numbers so that this becomes one of the defining characteristics of the natural numbers.
The Principle of Mathematical Induction
If \(T\) is a subset of \(\mathbb{N}\) such that
- \(1 \in T\), and
- For every \(k \in \mathbb{N}\), if \(k \in T\), then \((k + 1) \in T\).
Then \(T = \mathbb{N}\).
Using the Principle of Mathematical Induction
The primary use of the Principle of Mathematical Induction is to prove statements of the form
\((\forall n \in \mathbb{N}) (P(n))\).
where \(P(n)\) is some open sentence. Recall that a universally quantified statement like the preceding one is true if and only if the truth set T of the open sentence \(P(n)\) is the set \(\mathbb{N}\). So our goal is to prove that \(T = \mathbb{N}\), which is the conclusion of the Principle of Mathematical Induction. To verify the hypothesis of the Principle of Mathematical Induction, we must
- Prove that \(1 \in T\). That is, prove that \(P(1)\) is true.
- Prove that if \(k \in T\), then \((k + 1) \in T\). That is, prove that if \(P(k)\) is true, then \(P(k + 1)\) is true.
The first step is called the basis step or the initial step, and the second step is called the inductive step. This means that a proof by mathematical induction will have the following form:
Procedure for a Proof by Mathematical Induction
To prove: \((\forall n \in \mathbb{N}) (P(n))\)
Basis step: Prove \(P(1)\).\
Inductive step: Prove that for each \(k \in \mathbb{N}\), if \(P(k)\) is true, then \(P(k + 1)\) is true.
We can then conclude that \(P(n)\) is true for all \(n \in \mathbb{N}\)
Note that in the inductive step, we want to prove that the conditional statement “for each \(k \in \mathbb{N}\), if \(P(k)\) then \(P(k + 1)\)” is true. So we will start the inductive step by assuming that \(P(k)\) is true. This assumption is called the inductive assumption or the inductive hypothesis.
The key to constructing a proof by induction is to discover how \(P(k + 1)\) is related to \(P(k)\) for an arbitrary natural number \(k\). For example, in Preview Activity \(\PageIndex{1}\), one of the open sentences \(P(n)\) was
\(1^2 + 2^2 + ... + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}.\)
Sometimes it helps to look at some specific examples such as \(P(2)\) and \(P(3)\). The idea is not just to do the computations, but to see how the statements are related. This can sometimes be done by writing the details instead of immediately doing computations.
\begin{eqnarray}
\ \ \ \ \ &P(2)&\ \ \ \ \ \ \ \ \ &is& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1^2 + 2^2 &=& \dfrac{2 \cdot 3 \cdot 5}{6}\\
\ \ \ \ \ &P(3)&\ \ \ \ \ \ \ \ \ &is& \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1^2 + 2^2 + 3^2 &=& \dfrac{3 \cdot 4 \cdot 7}{6}
\end{eqnarray}
In this case, the key is the left side of each equation. The left side of \(P(3)\) is obtained from the left side of \(P(2)\) by adding one term, which is \(3^2\). This suggests that we might be able to obtain the equation for \(P(3)\) by adding \(3^2\) to both sides of the equation \(P(2)\). Now for the general case, if \(k \in \mathbb{N}\), we look at \(P(k + 1)\) and compare it to \(P(k)\).
\begin{eqnarray}
\ \ \ \ \ P(k)\ \ \ &is&\ \ \ \ \ \ \ \ \ \ \ 1^2 + 2^2 + ... + k^2 = \dfrac{k(k + 1)(2k + 1)}{6}\\
\ \ \ P(k + 1)\ \ &is&\ \ 1^2 + 2^2 + ... + (k + 1)^2 = \dfrac{(k + 1)[(k + 1) + 1][2(k + 1) + 1]}{6}
\end{eqnarray}
The key is to look at the left side of the equation for \(P(k + 1)\) and realize what this notation means. It means that we are adding the squares of the first \(k + 1\) natural numbers. This means that we can write
\(1^2 + 2^2 + ... + (k + 1)^2 = 1^2 + 2^2 + ... + k^2 + (k + 1)^2.\)
This shows us that the left side of the equation for \(P(k + 1)\) can be obtained from the left side of the equation for \(P(k)\) by adding \((k + 1)^2\). This is the motivation for proving the inductive step in the following proof.
Proposition 4.2.
For each natural number \(n\),
\(1^2 + 2^2 + ... + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}.\)
- Proof
-
We will use a proof by mathematical induction. For each natural number \(n\), we let \(P(n)\) be
\(1^2 + 2^2 + ... + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}.\)
We first prove that \(P(1)\) is true. Notice that \(\dfrac{1(1 + 1)(2 \cdot 1 + 1)}{6} = 1\). This shows that
\(1^2 = \dfrac{1(1 + 1)(2 \cdot 1 + 1}{6},
which proves that \(P(1)\) is true.
For the inductive step, we prove that for each \(k \in \mathbb{N}\), if \(P(k)\) is true, then \(P(k + 1)\) is true. So let \(k\) be a natural number and assume that \(P(k)\) is true. That is, assume that
\[1^2 + 2^2 + ... + k^2 = \dfrac{k(k + 1)(2k + 1)}{6}.\]
The goal now is to prove that \(P(k + 1)\) is true. That is, it must be proved that
\begin{eqnarray}
1^2 + 2^2 + ... + k^2 + (k + 1)^2 &=& \dfrac{(k + 1)[(k + 1) + 1][2(k + 1) + 1]}{6}\\
&=& \dfrac{(k + 1)(k + 2)(2k + 3)}{6}.
\end{eqnarray}To do this, we add \((k + 1)^2\) to both sides of equation (1) and algebraically rewrite the right side of the resulting equation. This gives
\begin{eqnarray}
1^2 + 2^2 + ... + k^2 + (k + 1)^2 &=& \dfrac{k(k + 1)(2k + 1)}{6} + (k + 1)^2\\
&=& \dfrac{k(k + 1)(2k + 1) + 6(k + 1)^2}{6}\\
&=& \dfrac{(k + 1)[k(2k + 1) + 6(k + 1)]}{6}\\
&=& \dfrac{(k + 1)(2k^2 + 7k + 6)}{6}\\
&=& \dfrac{(k + 1)(k + 2)(2k + 3) + 6(k + 1)^2}{6}
\end{eqnarray}Comparing this result to equation (2), we see that if \(P(k)\) is true, then \(P(k + 1)\) is true. Hence, the inductive step has been established, and by the Principle of Mathematical Induction, we have proved that for each natural number \(n\), \(1^2 + 2^2 + ... + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}.\)
Writing Guideline
The proof of Proposition 4.2 shows a standard way to write an induction proof. When writing a proof by mathematical induction, we should follow the guideline that we always keep the reader informed. This means that at the beginning of the proof, we should state that a proof by induction will be used. We should then clearly define the open sentence (P(n)\) that will be used in the proof.
Summation Notation
The result in Proposition 4.2 could be written using summation notation as follows:
\begin{equation*}
\text{For each natural number \(n\)}, \sum_{j=1}^n j^2 = \dfrac{n(n + 1)(2n + 1)}{6}.
\end{equation*}
In this case, we use \(j\) for the index for the summation, and the notation \(\sum_{j=1}^n j^2\) tells us to add all the values of \(j^2\) for \(j\) from 1 to \(n\), inclusive. That is,
\begin{equation*}
\sum_{j=1}^n j^2 = 1^2 + 2^2 + ... + n^2.
\end{equation*}
So in the proof of Proposition 4.2, we would let \(P(n)\) be \(\sum_{j=1}^n j^2 = \dfrac{n(n + 1)(2n + 1)}{6}\), and we would use the fact that for each natural number \(k\),
\begin{equation*}
\sum_{j=1}^{k+1} j^2 = (\sum_{j=1}^{k} j^2) + (k + 1)^2.
\end{equation*}
Progress Check 4.3 (An Example of a Proof by Induction)
- Calculate \(1 + 2 + 3 + ... + n\) and \(\dfrac{n(n+1)}{2}\) for several natural numbers \(n\). What do you observe?
- Use mathematical induction to prove that \(1 + 2 + 3 + ... + n = \dfrac{n(n+1)}{2}\). To do this, let \(P(n)\) be the open sentence, "\(1 + 2 + 3 + ... + n = \dfrac{n(n+1)}{2}\)." For the basis step, notice that the equation \(1 = \dfrac{1(1 + 1)}{2}\) shows that \(P(1)\) is true. Now let \(k\) be a natural number and assume that \(P(k)\) is true. That is, assume that
\[1 + 2 + 3 + ... + k = \dfrac{k(k+1)}{2},\]
and complete the proof.
- Answer
-
Add texts here. Do not delete this text first.
Some Comments about Mathematical Induction
- The basis step is an essential part of a proof by induction. See Exercise (19) for an example that shows that the basis step is needed in a proof by induction.
- Exercise (20) provides an example that shows the inductive step is also an essential part of a proof by mathematical induction.
- It is important to remember that the inductive step in an induction proof is a proof of a conditional statement. Although we did not explicitly use the forward-backward process in the inductive step for Proposition 4.2, it was implicitly used in the discussion prior to Proposition 4.2. The key question was, “How does knowing the sum of the first \(k\) squares help us find the sum of the first \((k + 1)\) squares?”
- When proving the inductive step in a proof by induction, the key question is,
How does knowing \(P(k)\) help us prove \(P(k + 1)\)?
In Proposition 4.2, we were able to see that the way to answer this question was to add a certain expression to both sides of the equation given in \(P(k)\). Sometimes the relationship between \(P(k)\) and \(P(k + 1)\) is not as easy to see. For example, in Preview Activity \(\PageIndex{1}\), we explored the following proposition:
For each natural number \(n\), 4 divides \((5^n - 1)\).
This means that the open sentence, \(P(n)\), is "4 divides \((5^n - 1)\)." So in the inductive step, we assume \(k \in \mathbb{N}\) and that 4 divides \((5^k - 1)\). This means that there exists an integer \(m\) such that
\[5^k - 1 = 4m.\]
In the backward process, the goal is to prove that 4 divides \((5^{k+1} - 1)\). This can accomplished if we can prove that there exists an integer \(s\) such that
\[5^{k+1} - 1 = 4s.\]
We now need to see if there is anything in equation (4.1.15) that can be used in equation (4.1.16). The key is to find something in the equation \(5^k - 1 = 4m\) that is related to something similar in the equation \(5^{k+1} - 1 = 4s\) In this case, we notice that
\[5^{k+1} = 5 \cdot 5^k.\]
So if we can solve \(5^k - 1 = 4m\) for \(5^k\), we could make a substitution for \(5^k\). This is done in the proof of the following proposition.
Proposition 4.4.
For every natural number \(n\), 4 divides \((5^n - 1)\).
- Proof
-
(Proof by Mathematical Induction) For each natural number \(n\), let \(P(n)\) be “4 divides \((5^n - 1)\)” We first prove that \(P(1)\) is true. Notice that when \(n = 1\), \(5^n - 1 = 4\). Since 4 divides 4, \(P(1)\) is true.
For the inductive step, we prove that for all \(k \in \mathbb{N}\), if \(P(k)\) is true, then \(P(k + 1)\) is true. So let \(k\) be a natural number and assume that \(P(k)\) is true. That is, assume that
4 divides \((5^k - 1)\).
This means that there exists an integer \(m\) such that
\(5^k - 1 = 4m.\)
Thus,
\[5^k = 4m + 1.\]
In order to prove that \(P(k + 1)\) is true, we must show that 4 divides \((5^{k+1} - 1)\). Since \(5^{k+1} = 5 \cdot 5^k\), we can write
\[5^{k+1} - 1 = 5 \cdot 5^k - 1.\]
We now substitute the expression for 5k from equation (4.1.18) into equation (4.1.19). This gives
\[\begin{array} {lll} {5^{k + 1} - 1} &{=} &{5\cdot 5^{k} - 1} \\ {} &{=} &{5(4m + 1) - 1} \\ {} &{=} &(20m + 5) - 1\\ {} &{=} & 20m + 4\\ {} &{=} & 4(5m + 1) \end{array}\]
Since \((5m + 1)\) is an integer, equation (4.1.20) shows that 4 divides \((5^{k+1} - 1)\). Therefore, if \(P(k)\) is true, then \(P(k + 1)\) is true and the inductive step has been established. Thus, by the principle of Mathematical Induction, for every natural number \(n\), 4 divides \((5^{n} - 1)\).
Proposition 4.4 was stated in terms of “divides.” We can use congruence to state a proposition that is equivalent to Proposition 4.4. The idea is that the sentence, 4 divides \((5^{n} - 1)\) means that \(5^n \equiv 1\) (mod 4). So the following proposition is equivalent to Proposition 4.4.
Proposition 4.5.
For every natural number \(n\), \(5^n \equiv 1\) (mod 4).
Since we have proved Proposition 4.4, we have in effect proved Proposition 4.5. However, we could have proved Proposition 4.5 first by using the results in Theorem 3.28 on page 147. This will be done in the next progress check.
Progress Check 4.6 (Proof of Proposition 4.5) .
To prove Proposition 4.5, we let \(P(n)\) be \(5^n \equiv 1\) (mod 4) and notice that \(P(1)\) is true since \(5 \equiv 1\) (mod 4). For the inductive step, let \(k\) be a natural number and assume that \(P(k)\) is true. That is, assume that \(5^n \equiv 1\) (mod 4).
- What must be proved in order to prove that \(P(k + 1)\) is true?
- Since \(5^{k+1} = 5 \cdot 5^k\), multiply both sides of the congruence \(5^k \equiv 1\) (mod 4) by 5. The results in Theorem 3.28 on page 147 justify this step.
- Now complete the proof that for each \(k \in \mathbb{N}\), if \(P(k)\) is true, then \(P(k + 1)\) is true and complete the induction proof of Proposition 4.5.
It might be nice to compare the proofs of Propositions 4.4 and 4.5 and decide which one is easier to understand.
- Answer
-
Add texts here. Do not delete this text first.
Exercises for Section 4.1
- Which of the following sets are inductive sets? Explain.
(a) \(\mathbb{Z}\)
(b) \(\{x \in \mathbb{N} | x \ge 4\}\)
(c) \(\{x \in \mathbb{Z} | x \le 10\}\)
(d) {1, 2, 3, ..., 500} - (a) Can a finite, nonempty set be inductive? Explain.
(b) Is the empty set inductive? Explain. - Use mathematical induction to prove each of the following:
(a) For each natural number \(n\), \(2 + 5 + 8 + \cdot\cdot\cdot + (3n - 1) = \dfrac{n(3n+1)}{2}\).
(b) For each natural number \(n\), \(1 + 5 + 9 + \cdot\cdot\cdot + (4n - 3) = n(2n - 1)\).
(c) For each natural number \(n\), \(1^3 + 2^3 + 3^3 + \cdot\cdot\cdot + n^3 = [\dfrac{n(n+1)}{2}]^2\). - Based on the results in Progress Check 4.3 and Exercise (3c), if \(n \in \mathbb{N}\), is there any conclusion that can be made about the relationship between the sum \((1^3 + 2^3 + 3^3 + ... + n^3)\) and the sum \((1 + 2 + 3 + \cdot\cdot\cdot + n)\)?
- Instead of using induction, we can sometimes use previously proven results about a summation to obtain results about a different summation.
(a) Use the result in Progress Check4.3 to prove the following proposition:
\[\text{For each natural number \(n\)}, 3 + 6 + 9 + ... + 3n = \dfrac{3n(n + 1)}{2}.\]
(b) Subtract \(n\) from each side of the equation in Part (a). On the left side of this equation, explain why this can be done by subtracting 1 from each term in the summation.
(c) Algebraically simplify the right side of the equation in Part (b) to obtain a formula for the sum \(2 + 5 + 8 + ... (3n - 1).\) Compare this to Exercise (3a). - (a) Calculate \(1 + 3 + 5 + \cdot\cdot\cdot + (2n - 1)\) for several nuatural numbers \(n\).
(b) Based on your work in exercise (6a), if \(n \in \mathbb{N}\), make a conjecture about the value of the sum \(1 + 3 + 5 + \cdot\cdot\cdot + (2n - 1) = \sum_{j = 1}^n (2j - 1).\)
(c) Use mathematical induction to prove your conjecture in Exercise (6b). - In Section 3.1, we defined congruence modulo \(n\) for a natural number \(n\), and in Section 3.5, we used the Division Algorithm to prove that each integer is congruent, modulo \(n\), to precisely one of the integers 0, 1, 2, \cdot\cdot\cdot, \(n - 1\)(Corollary 3.32).
(a) Find the value of \(r\) so that \(4 \equiv r\) (mod 3) and \(r \in \{0, 1, 2\}\).
(b) Find the value of \(r\) so that \(4^2 \equiv r\) (mod 3) and \(r \in \{0, 1, 2\}\).
(c) Find the value of \(r\) so that \(4^3 \equiv r\) (mod 3) and \(r \in \{0, 1, 2\}\).
(d) For two other values of \(n\), find the value of \(r\) so that \(4^n \equiv r\) (mod 3) and \(r \in \{0, 1, 2\}\).
(e) If \(n \in \mathbb{N}\) make a conjecture concerning the value of \(r\) where \(4^n \equiv r\) (mod 3) and \(r \in \{0, 1, 2\}\). This conjecture should be written as a self-contained proposition including an appropriate quantifier.
(f) Use mathematical induction to prove your conjecture. - Use mathematical induction to prove each of the following:
(a) For each natural number \(n\), 3 divides \((4^n - 1)\).
(b) For each natural number \(n\), 6 divides \((n^3 - n)\). - In Exercise (7), we proved that for each natural number \(n\), \(4^n \equiv 1\) (mod 3). Explain how this result is related to the proposition in Exercise (8a).
- Use mathematical induction to prove that for each natural number \(n\), 3 divides \(n^3 + 23n\). Compare this proof to the proof from Exercise (18) in Section 3.5.
- (a) Calculate the value of \(5^n - 2^n\) for \(n = 1, n = 2, n = 3, n = 4, n = 5\) and \(n = 6\).
(b) Based on your work in Part (a), make a conjecture about the values of \(5^n - 2^n\) for each natural number \(n\).
(c) Use mathematical induction to prove your conjecture in Part (b). - Let \(x\) and \(y\) be integers. Prove that for each natural number \(n\), \((x - y)\) divides \((x^n - y^n)\). Explain why your conjecture in Exercise (11) is a special case of this result.
- Prove Part (3) of Theorem 3.28 from Section 3.4. Let \(n \in \mathbb{N}\) and let \(a\) and \(b\) be integers. For each \(m \in \mathbb{N}\), if \(a \equiv b\) (mod \(n\)), then \(a^m \equiv b^m\) (mod \(n\)).
- Use mathematical induction to prove that the sum of the cubes of any three consecutive natural numbers is a multiple of 9.
- Let \(a\) be a real number. We will explore the derivatives of the function \(f(x) = e^{ax}\). By using the chain rule, we see that
\[\dfrac{d}{dx}(e^{ax}) = ae^{ax}.\]
Recall that the second derivative of a function is the derivative of the derivative function. Similarly, the third derivative is the derivative of the second derivative.(a) What is \(\dfrac{d^2}{dx^2}(e^{ax})\), the second derivative of \(e^{ax}\)?
(b) What is \(\dfrac{d^3}{dx^3}(e^{ax})\), the third derivative of \(e^{ax}\)?
(c) Let \(n\) be a natural number. Make a conjecture about the \(n\)th derivatives of the function \(f(x) = e^{ax}\). That is, what is \(\dfrac{d^n}{dx^n}(e^{ax})\)? This conjecture should be written as a self-contained proposition including an appropriate quantifier.
(d) Use mathematical induction to prove that your conjecture. - In calculus, it can be shown that
\[\begin{array} {lll} {\int sin^2 x dx} &= & {\dfrac{x}{2} - \dfrac{1}{2} sinx cosx + c \ \ \text{and}} \\ {\int cos^2 x dx} &= & {\dfrac{x}{2} + \dfrac{1}{2} sinx cosx + c.}\end{array}\]
Using integration by parts, it is also possible to prove that for each natural number \(n\),
\[\begin{array} {lll} {\int sin^n x dx} &= & {-\dfrac{1}{n} sin^{n - 1} x cosx + \dfrac{n - 1}{n} \int sin^{n - 2} x dx \ \ \text{and}} \\ {\int cos^n x dx} &= & {\dfrac{1}{n} cos^{n - 1} x sinx + \dfrac{n - 1}{n} \int cos^{n - 2} x dx.}\end{array}\](a) Determine the values of
\[\int_{0}^{\pi /2} sin^2 x dx \ \ \ \text{and} \ \ \ \int_{0}^{\pi /2} sin^4 x dx.\]
(b) Use mathematical induction to prove that for each natural number \(n\)
\[\begin{array} {lll} {\int_{0}^{\pi /2} sin^{2n} x dx} &= & {\dfrac{1 \cdot 3 \cdot 5 \cdot\cdot\cdot (2n - 1)}{2 \cdot 4 \cdot 6 \cdot\cdot\cdot (2n)}\dfrac{\pi}{2} \ \ \ \text{and}} \\ {\int_{0}^{\pi /2} sin^{2n + 1} x dx} &= & \dfrac{2 \cdot 4 \cdot 6 \cdot\cdot\cdot (2n)}{1 \cdot 3 \cdot 5 \cdot\cdot\cdot (2n + 1).} \end{array}\]
These are known as the Wallis sine formulas.
(c) Use mathematical induction to prove that
\[\begin{array} {lll} {\int_{0}^{\pi /2} cos^{2n} x dx} &= & {\dfrac{1 \cdot 3 \cdot 5 \cdot\cdot\cdot (2n - 1)}{2 \cdot 4 \cdot 6 \cdot\cdot\cdot (2n)}\dfrac{\pi}{2} \ \ \ \text{and}} \\ {\int_{0}^{\pi /2} cos^{2n + 1} x dx} &= & \dfrac{2 \cdot 4 \cdot 6 \cdot\cdot\cdot (2n)}{1 \cdot 3 \cdot 5 \cdot\cdot\cdot (2n + 1).} \end{array}\]
These are known as the Wallis cosine formulas. - (a) Why is it not possible to use mathematical induction to prove a proposition of the form
\[(\forall x \in \mathbb{Q}) (P(x)),\]
where \(P(x)\) is some predicate?
(b) Why is it not possible to use mathematical induction to prove a proposition of the form
For each real number \(x\) with \(x \ge 1\), \(P(x)\),
where \(P(x) is some predicate? - Evaluation of proofs
See the instructions for Exercise (19) on page 100 from Section 3.1.(a)
For each natural number \(n\), \(1 + 4 + 7 + \cdot\cdot\cdot + (3n - 2) = \dfrac{n(3n -1)}{2}.\)
- Proof
-
We will prove this proposition using mathematical induction. So we let \(P(n)\) be the open sentence
\(1 + 4 + 7 + \cdot\cdot\cdot + (3n - 2).\)
Using \(n= 1\), we see taht \(3n - 2 = 1\) and hence, \(P(1)\) is true.
We now assume taht \(P(k)\) is true. That is,
\(1 + 4 + 7 + \cdot\cdot\cdot + (3k - 2) = \dfrac{k(3k - 1)}{2}.\)
We then see that
\[\begin{array} {rcc} {1 + 4 + 7 + \cdot\cdot\cdot + (3k - 2) + (3(k + 1) - 2)} &= & {\dfrac{(k+1)(3k + 2)}{2}} \\ {\dfrac{k(3k - 1)}{2} + (3k + 1)} &= & {\dfrac{(k+1)(3k + 2)}{2}} \\ {\dfrac{(3k^2 - k) + (6k + 2)}{2}} &= & {\dfrac{3k^2 + 5k + 2}{2}} \\ {\dfrac{3k^2 + 5k + 2}{2}} &= & {\dfrac{3k^2 + 5k + 2}{2}}.\end{array}\]
We have thus proved that \(P(k+1)\) is true, and hence, we have proved the proposition.
(b)
For each natural number \(n\), \(1 + 4 + 7 + \cdot\cdot\cdot + (3n - 2) = \dfrac{n(3n -1)}{2}.\)
- Proof
-
We will prove this proposition using mathematical induction. So we let
\(P(n) = 1 + 4 + 7 + \cdot\cdot\cdot + (3n - 2)\).
Using \(n = 1\), we see that \(P(1) = 1\) and hence, \(P(1)\) is true.
We now assume that \(P(k)\) is true. That is,
\(1 + 4 + 7 + \cdot\cdot\cdot + (3k - 2) = \dfrac{k(3k - 1)}{2}.\)
We then see that
\[\begin{array} {lcl} {P(k + 1)} &= & {1 + 4 + 7 + \cdot\cdot\cdot + (3k - 2) + (3(k + 1) - 2)} \\ {} &= & {\dfrac{k(3k - 2)}{2} + 3(k + 1) - 2} \\ {} &= & {\dfrac{3k^2 - k + 6k + 6 - 4}{2}} \\ {} &= & {\dfrac{3k^2 + 5k + 2}{2}} \\ {} &= & {\dfrac{(k + 1)(3k + 2)}{2}}.\end{array}\]
we have thus proved that \(P(k + 1)\) is true, and hence, we have proved the proposition.
(c)
All dogs are the same breed.
- Proof
-
We will prove this proposition using mathematical induction. For each natural number \(n\), we let \(P(n)\) be
Any set of \(n\) dogs consists entirely of dogs of the same breed.
We will prove that for each natural number \(n\), \(P(n)\) is true, which will prove that all dogs are the same breed. A set with only one dog consists entirely of dogs of the same breed and, hence, \(P(1)\) is true.
So we let \(k\) be a natural number and assume that \(P(k)\) is true, that is, that every set of \(k\) dogs consists of dogs of the same breed. Now consider a set \(D\) of \(k + 1\) dogs, where
\(D = \{d_1, d_2, ..., d_k, d_{k + 1}\}.\)
If we remove the dog \(d_1\) from the set \(D\), we then have a set \(D_1\) of \(k\) dogs, and using the assumption that \(P(k)\) is true, these dogs must all be of the same breed. Similarly, if we remove \(d_{k + 1}\) from the set \(D\), we again have a set \(D_2\) of \(k\) dogs, and these dogs must all be of the same breed. Since \(D = D_1 \cup D_2\), we have proved that all of the dogs in \(D\) must be of the same breed.
This proves that if \(P(k)\) is true, then \(P(k + 1)\) is true and, hence, by mathematical induction, we have proved that for each natural number \(n\), any set of \(n\) dogs consists entirely of dogs of the same breed.
Explorations and Activities
- The Importance of the Basis Step. Most of the work done in constructing a proof by induction is usually in proving the inductive step. This was certainly the case in Proposition 4.2. However, the basis step is an essential part of the proof. Without it, the proof is incomplete. To see this, let \(P(n)\) be
\[1 + 2 + \cdot\cdot\cdot + n = \dfrac{n^2 + n + 1}{2}.\](a) Let \(k \in \mathbb{N}\). Complete the following proof that if \(P(k)\) is true, then \(P(k + 1)\) is true.
Let \(k \in mathbb{N}\). Assume that \(P(k)\) is true. That is, assume that
\[1 + 2 + \cdot\cdot\cdot + k = \dfrac{k^2 + k + 1}{2}.\]
The goal is to prove that \(P(k + 1)\) is true. That is, we need to prove that
\[1 + 2 + \cdot\cdot\cdot + k + (k + 1) = \dfrac{(k + 1)^2 + (k + 1) + 1}{2}.\]
To do this, we add \(k + 1\) to both sides of equation (4.1.32). This gives
\[\begin{array} {rcl} {1 + 2 + \cdot\cdot\cdot + k + (k + 1)} &= & {\dfrac{k^2 + k + 1}{2} + (k + 1)} \\ {} &= & {\cdot\cdot\cdot}.\end{array}\]
(b) Is \(P(1)\) true? Is \(P(2)\) true? What about \(P(3)\) and \(P(4)\)? Explain how this shows that the basis step is an essential part of a proof by induction. - Regions of a Circle. Place n equally spaced points on a circle and connect each pair of points with the chord of the circle determined by that pair of points. See Figure 4.1.
Count the number of distinct regions within each circle. For example, with three points on the circle, there are four distinct regions. Organize your data in a table with two columns: “Number of Points on the Circle” and “Number of Distinct Regions in the Circle.”(a) How many regions are there when there are four equally spaced points on the circle?
(b) Based on the work so far, make a conjecture about how many distinct regions would you get with five equally spaced points.
(c) Based on the work so far, make a conjecture about how many distinct regions would you get with six equally spaced points.
(d) Figure 4.2 shows the figures associated with Parts (b) and (c). Count the number of regions in each case. Are your conjectures correct or incorrect?
(e) Explain why this activity shows that the inductive step is an essential part of a proof by mathematical induction.
- Answer
-
Add texts here. Do not delete this text first.
