2.6: Strong Mathematical Induction
- Page ID
- 9675
\( \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}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)There is a second form of the principle of mathematical induction which is useful in some cases. To apply the first form of induction, we assume P(k) for an arbitrary natural number k and show that P(k + 1) follows from that assumption. In the second form of induction, the assumption is that P(x) holds for all x between 0 and k inclusive, and we show that P(k + 1) follows from this. This gives us a lot more to work with when deducing P(k + 1). We will need this second, stronger form of induction in the next two sections. A proof will be given in the next chapter.
Theorem 3.9.
Let P be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that P(0) is true and that
\((P(0) \wedge P(1) \wedge \cdots \wedge P(k)) \rightarrow P(k+1)\)
is true for each natural number k ≥ 0. Then P(n) is true for every natural number n.
For example, we can use this theorem to prove that every integer greater than one can be written as a product of prime numbers (where a number that is itself prime is considered to be a product of one prime number). The proof illustrates an important point about applications of this theorem: When proving P(k + 1), you don’t necessarily have to use the assumptions that P(0), P(1), ..., and P(k) are true. If P(k + 1) is proved by any means—possibly including the assumptions—then the statement (P(0) ∧ P(1) ∧ · · · ∧ P(k)) → P(k + 1) has been shown to be true. It follows from this observation that several numbers, not just zero, can be ‘base cases’ in the sense that P(x + 1) can be proved independently of P(0) through P(x). In this sense, 0, 1, and every prime number are base cases in the following theorem.
Theorem 3.10.
Every natural number greater than one can be written as a product of prime numbers.
Proof. Let P(n) be the statement “if n > 1, then n can be written as a product of prime numbers”. We will prove that P(n) is true for all n by applying the second form of the principle of induction.
Note that P(0) and P(1) are both automatically true, since n = 0 and n = 1 do not satisfy the condition that n > 1, and P(2) is true since 2 is the product of the single prime number 2. Suppose that k is an arbitrary natural number with k > 1, and suppose thatP(0), P(1), ..., P(k) are already known to be true; we want to show that P(k + 1) is true. In the case where k + 1 is a prime number, then k + 1 is a product of one prime number, so P(k + 1) is true.
Consider the case where k + 1 is not prime. Then, according to the definition of prime number, it is possible to write k + 1 = ab where a and b are numbers in the range from 2 to k inclusive. Since P(0) through P(k) are known to be true, a and b can each be written as a product of prime numbers. Since k + 1 = ab, k + 1 can also be written as a product of prime numbers. We have shown that P(k + 1) follows from P(0) ∧ P(1) ∧ · · · ∧ P(k), and this completes the induction.
In two of the pencasts of this course, we treat two flawed induction proofs and examine what mistakes have been made. You can find them here: youtu. be/m0EIgQyukdQ and youtu.be/2c-zw-ENNss.
Exercises
1. Use induction to prove that \(n^{3}+3 n^{2}+2 n\) is divisible by 3 for all natural numbers \(n\)
2. Use induction to prove that
\(\sum_{i=0}^{n} r^{i}=\frac{1-r^{n+1}}{1-r}\)
for any natural number n and for any real number r such that r \(\neq\) 1.
3. Use induction to prove that for any natural number n,
\(\sum_{i=0}^{n} \frac{1}{2^{i}}=2-\frac{1}{2^{n}}\)
In addition to proving this by induction, show that it follows as a corollary of Exercise 2.
- Use induction to prove that for any natural number n,
\(\sum_{i=0}^{n} 2^{i}=2^{n+1}-1\)
In addition to proving this by induction, show that it follows as a corollary of Exercise 2.
5. Use induction to prove that for any positive integer n,
\(\sum_{i=1}^{n} i^{2}=\frac{n(n+1)(2 n+1)}{6}\)
- Use induction to prove that for any positive integer n,
\(\sum_{i=1}^{n}(2 i-1)=n^{2}\)
7. Evaluate the following sums, using results proved in this section and in the previous exercises:
a) 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 + 19
b) \(1+\frac{1}{3}+\frac{1}{3^{2}}+\frac{1}{3^{3}}+\frac{1}{3^{4}}+\frac{1}{3^{5}}+\frac{1}{3^{6}}\)
c) 50 + 51 + 52 + 53 + · · · + 99 + 100
d)1 + 4 + 9 + 16 + 25 + 36 + 49 + 81 + 100
e)\(\frac{1}{2^{2}}+\frac{1}{2^{3}}+\dots+\frac{1}{2^{99}}\)
- Write each of the sums in the preceding problem using summation notation.
- Rewrite the proof of Theorem 3.8 without using summation notation.
- Use induction to prove the following generalized distributive laws for propositional logic: For any natural number \(n>1\) and any propositions \(q, p_{1}, p_{2}, \ldots, p_{n}\)
a) \(q \wedge\left(p_{1} \vee p_{2} \vee \cdots \vee p_{n}\right)=\left(q \wedge p_{n}\right) \vee\left(q \wedge p_{2}\right) \vee \cdots \vee\left(q \wedge p_{n}\right)\)
b) \(q \vee\left(p_{1} \wedge p_{2} \wedge \cdots \wedge p_{n}\right)=\left(q \vee p_{1}\right) \wedge\left(q \vee p_{2}\right) \wedge \cdots \wedge\left(q \vee p_{n}\right)\)