2.1: Mathematical Induction
- Page ID
- 81031
\( \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}\)Suppose we wish to show that
\[ 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} \nonumber \]
for any natural number \(n\text{.}\) This formula is easily verified for small numbers such as \(n = 1\text{,}\) \(2\text{,}\) \(3\text{,}\) or \(4\text{,}\) but it is impossible to verify for all natural numbers on a case-by-case basis. To prove the formula true in general, a more generic method is required.
Suppose we have verified the equation for the first \(n\) cases. We will attempt to show that we can generate the formula for the \((n + 1)\)th case from this knowledge. The formula is true for \(n = 1\) since
\[ 1 = \frac{1(1 + 1)}{2}\text{.} \nonumber \]
If we have verified the first \(n\) cases, then
\begin{align*} 1 + 2 + \cdots + n + (n + 1) & = \frac{n(n + 1)}{2} + n + 1\\ & = \frac{n^2 + 3n + 2}{2}\\ & = \frac{(n + 1)[(n + 1) + 1]}{2}\text{.} \end{align*}
This is exactly the formula for the \((n + 1)\)th case.
This method of proof is known as mathematical induction. Instead of attempting to verify a statement about some subset \(S\) of the positive integers \({\mathbb N}\) on a case-by-case basis, an impossible task if \(S\) is an infinite set, we give a specific proof for the smallest integer being considered, followed by a generic argument showing that if the statement holds for a given case, then it must also hold for the next case in the sequence. We summarize mathematical induction in the following axiom.
Let \(S(n)\) be a statement about integers for \(n \in {\mathbb N}\) and suppose \(S(n_0)\) is true for some integer \(n_0\text{.}\) If for all integers \(k\) with \(k \geq n_0\text{,}\) \(S(k)\) implies that \(S(k+1)\) is true, then \(S(n)\) is true for all integers \(n\) greater than or equal to \(n_0\text{.}\)
For all integers \(n \geq 3\text{,}\) \(2^n \gt n + 4\text{.}\) Since
\[ 8 = 2^3 \gt 3 + 4 = 7\text{,} \nonumber \]
the statement is true for \(n_0 = 3\text{.}\) Assume that \(2^k \gt k + 4\) for \(k \geq 3\text{.}\)
Solution
Then \(2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\text{.}\) But
\[ 2(k + 4) = 2k + 8 \gt k + 5 = (k + 1) + 4 \nonumber \]
since \(k\) is positive. Hence, by induction, the statement holds for all integers \(n \geq 3\text{.}\)
Every integer \(10^{n + 1} + 3 \cdot 10^n + 5\) is divisible by \(9\) for \(n \in {\mathbb N}\text{.}\) For \(n = 1\text{,}\)
\[ 10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15 \nonumber \]
is divisible by \(9\text{.}\) Suppose that \(10^{k + 1} + 3 \cdot 10^k + 5\) is divisible by \(9\) for \(k \geq 1\text{.}\)
Solution
Then
\begin{align*} 10^{(k + 1) + 1} + 3 \cdot 10^{k + 1} + 5& = 10^{k + 2} + 3 \cdot 10^{k + 1} + 50 - 45\\ & = 10 (10^{k + 1} + 3 \cdot 10^{k} + 5) - 45 \end{align*}
is divisible by \(9\text{.}\)
We will prove the binomial theorem using mathematical induction; that is,
\[ (a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}\text{,} \nonumber \]
where \(a\) and \(b\) are real numbers, \(n \in \mathbb{N}\text{,}\) and
\[ \binom{n}{k} = \frac{n!}{k! (n - k)!} \nonumber \]
is the binomial coefficient.
Solution
We first show that
\[ \binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}\text{.} \nonumber \]
This result follows from
\begin{align*} \binom{n}{k} + \binom{n}{k - 1} & = \frac{n!}{k!(n - k)!} +\frac{n!}{(k-1)!(n - k + 1)!}\\ & = \frac{(n + 1)!}{k!(n + 1 - k)!}\\ & =\binom{n + 1}{k}\text{.} \end{align*}
If \(n = 1\text{,}\) the binomial theorem is easy to verify. Now assume that the result is true for \(n\) greater than or equal to \(1\text{.}\) Then
\begin{align*} (a + b)^{n + 1} & = (a + b)(a + b)^n\\ & = (a + b) \left( \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}\right)\\ & = \sum_{k = 0}^{n} \binom{n}{k} a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n + 1 - k}\\ & = a^{n + 1} + \sum_{k = 1}^{n} \binom{n}{k - 1} a^{k} b^{n + 1 - k} + \sum_{k = 1}^{n} \binom{n}{k} a^k b^{n + 1 - k} + b^{n + 1}\\ & = a^{n + 1} + \sum_{k = 1}^{n} \left[ \binom{n}{k - 1} + \binom{n}{k} \right]a^k b^{n + 1 - k} + b^{n + 1}\\ & = \sum_{k = 0}^{n + 1} \binom{n + 1}{k} a^k b^{n + 1- k}\text{.} \end{align*}
We have an equivalent statement of the Principle of Mathematical Induction that is often very useful.
Let \(S(n)\) be a statement about integers for \(n \in {\mathbb N}\) and suppose \(S(n_0)\) is true for some integer \(n_0\text{.}\) If \(S(n_0), S(n_0 + 1), \ldots, S(k)\) imply that \(S(k + 1)\) for \(k \geq n_0\text{,}\) then the statement \(S(n)\) is true for all integers \(n \geq n_0\text{.}\)
A nonempty subset \(S\) of \({\mathbb Z}\) is well-ordered if \(S\) contains a least element. Notice that the set \({\mathbb Z}\) is not well-ordered since it does not contain a smallest element. However, the natural numbers are well-ordered.
Every nonempty subset of the natural numbers is well-ordered.
The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.
The Principle of Mathematical Induction implies that \(1\) is the least positive natural number.
- Proof
-
Let \(S = \{ n \in {\mathbb N} : n \geq 1 \}\text{.}\) Then \(1 \in S\text{.}\) Assume that \(n \in S\text{.}\) Since \(0 \lt 1\text{,}\) it must be the case that \(n = n + 0 \lt n + 1\text{.}\) Therefore, \(1 \leq n \lt n + 1\text{.}\) Consequently, if \(n \in S\text{,}\) then \(n + 1\) must also be in \(S\text{,}\) and by the Principle of Mathematical Induction, and we have \(S = \mathbb N\text{.}\)
The Principle of Mathematical Induction implies the Principle of Well-Ordering. That is, every nonempty subset of \(\mathbb N\) contains a least element.
- Proof
-
We must show that if \(S\) is a nonempty subset of the natural numbers, then \(S\) contains a least element. If \(S\) contains 1, then the theorem is true by Lemma 2.7. Assume that if \(S\) contains an integer \(k\) such that \(1 \leq k \leq n\text{,}\) then \(S\) contains a least element. We will show that if a set \(S\) contains an integer less than or equal to \(n + 1\text{,}\) then \(S\) has a least element. If \(S\) does not contain an integer less than \(n+1\text{,}\) then \(n+1\) is the smallest integer in \(S\text{.}\) Otherwise, since \(S\) is nonempty, \(S\) must contain an integer less than or equal to \(n\text{.}\) In this case, by induction, \(S\) contains a least element.
Induction can also be very useful in formulating definitions. For instance, there are two ways to define \(n!\text{,}\) the factorial of a positive integer \(n\text{.}\)
- The explicit definition: \(n! = 1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n\text{.}\)
- The inductive or recursive definition: \(1! = 1\) and \(n! = n(n - 1)!\) for \(n \gt 1\text{.}\)
Every good mathematician or computer scientist knows that looking at problems recursively, as opposed to explicitly, often results in better understanding of complex issues.