7.3.3: Induction and Inequalities
- Page ID
- 14793
\( \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}\)Induction and Inequalities
This is the third in a series of lessons on mathematical proofs. In this lesson we continue to focus mainly on proof by induction, this time of inequalities, and other kinds of proofs such as proof by geometry.
Induction and Inequalities
The Transitive Property of Inequality
Below, we will prove several statements about inequalities that rely on the transitive property of inequality:
If a < b and b < c , then a < c.
Note that we could also make such a statement by turning around the relationships (i.e., using “greater than” statements) or by making inclusive statements, such as a ≥ b.
It is also important to note that this property of integers is a postulate, or a statement that we assume to be true. This means that we need not prove the transitive property of inequality.
You encountered other useful properties of inequalities in earlier algebra courses:
Addition property: if a > b , then a + c > b + c.
Multiplication property: if a > b, and c > 0 then ac > bc.
Examples
Prove that \(\ n ! \geq 2^{n}\) for \(\ n \geq 4\)
Solution
Step 1) The base case is n = 4: 4! = 24, 24 = 16. 24 ≥ 16 so the base case is true.
Step 2) Assume that k! ≥ 2k for some value of k such that k ≥ 4
Step 3) Show that (k+1)! ≥ 2k+1
| (k+1)! = k!(k+1) | Rewrite (k +1)! in terms of k ! |
|---|---|
| ≥ 2k(k +1) | Use step 2 and the multiplication property. |
| ≥ 2k(2) | k +1 ≥ 5 >2, so we can use the multiplication property again. |
| = 2k+1 |
Therefore n! ≥ 2n for n ≥ 4.
For what values of x is the inequality x > x2 true?
Solution
The inequality is true if x is a number between -1 and 1 but not 0.
Prove that 9n - 1 is divisible by 8 for all positive integers n.
Solution
| 1. Base case: | If n = 1, 9n - 1 = 9-1 = 8 = 8(1) |
|---|---|
| 2. Inductive hypothesis: | Assume that 9k - 1 is divisible by 8. |
| 3. Inductive step: | Show that 9k+1 - 1 is divisible by 8. |
| 9k - 1 divisible by 8 ⇒ 8W = (9k-1) for some integer W |
|---|
| 9k+1 - 1 = 9(9k - 1) + 8 = 9(8W) + 8,which is divisible by 8 |
Prove that \(\ 2^{n}<n !\) for all positive integers \(\ n\) where \(\ n \geq 4\).
Solution
Use the three steps of proof by induction:
Step 1) Base Case: \(\ 2^{4}<4 !\)
\(\ 2 \cdot 2 \cdot 2 \cdot 2<1 \cdot 2 \cdot 3 \cdot 4\)
\(\ 16<24\)..... This checks out
Step 2) Assumption: \(\ 2^{k}<k !\)
Step 3) Induction Step: starting with \(\ 2^{k}<k !\) prove \(\ 2^{k}(k+1)<k !(k+1)\)
\(\ 2^{k}(k+1)<(k+1) !\)
\(\ 2<k+1 \ldots \ldots\) If \(\ k \geq 4\) then this is true
\(\ 2^{k} \cdot 2<2^{k}(k+1) \ldots\) Multiply both sides by \(\ 2^{k}\)
\(\ 2^{k+1}<2^{k}(k+1)\)
\(\ 2^{k+1}<(k+1) !\)
\(\ \therefore 2^{n}<n !\) for all positive integers \(\ n\) where \(\ n \geq 4\)
Prove that \(\ n^{2}<3^{n}\) for all integers \(\ n>2\).
Solution
Use the three steps of proof by induction:
Step 1) Base Case: \(\ (n=1) 1^{2}<3^{1}\) or, if you prefer, \(\ (n=2) 2^{2}<3^{2}\)
Step 2) Assumption: \(\ k^{2}<3^{k}\)
Step 3) Induction Step: starting with \(\ k^{2}<3^{k}\) prove \(\ (k+1)^{2}<3^{k+1}\)
\(\ k^{2} \cdot 3<3^{k} \cdot 3\)
\(\ 2 k<k^{2} \text { and } 1<k^{2}\)..... assuming \(\ 2<k\) as specified in the question
\(\ 2 k+1<2 k^{2}\)..... combine the two statements above
\(\ k^{2}+2 k+1<3 k^{2}\)..... add \(\ k^{2}\) to both sides
\(\ (k+1)^{2}<3 k^{2}\)
\(\ (k+1)^{2}<3 \cdot 3^{k}\)..... from above
\(\ (k+1)^{2}<3^{k+1}\)
\(\ \therefore n^{2}<3^{n}\) for all integers \(\ n>2\)
Prove that \(\ 2 n+1<2^{n}\) for all integers \(\ n>3\)
Solution
Use the three steps of proof by induction:
Step 1) Base case: If \(\ n=3,2(3)+1=7,2^{3}=8: 7<8\), so the base case is true.
Step 2) Inductive hypothesis: Assume that \(\ 2 k+1<2^{k}\) for \(\ k>3\)
Step 3) Inductive step: Show that \(\ 2(k+1)+1<2^{k+1}\)
\(\ 2(k+1)+1=2 k+2+1=(2 k+1)+2<2^{k}+2<2^{k}+2^{k}=2\left(2^{k}\right)=2^{k+1}\)
Review
Prove the following inequalities.
- \(\ 5^{k}<(k+5) !\)
- \(\ 1^{k}<(k+1) !\)
- \(\ 4^{k}<(k+4) !\)
- \(\ 2^{k}<(k+2) !\)
- For what values of \(\ x\) is the inequality \(\ x>x^{2}\) true?
- Prove that \(\ 3^{n}>n^{2}\) for all positive integers \(\ n\).
Prove the following inequalities.
- \(\ \frac{1}{n+1}+\frac{1}{n+2}+\frac{1}{n+3}+\ldots+\frac{1}{2 n}>\frac{13}{24}(n>1)\)
- \(\ 2^{n} \geq n^{2}\) for \(\ n=4,5,6, \ldots\)
- \(\ \frac{1}{1^{2}}+\frac{1}{2^{2}}+\frac{1}{3^{2}}+\ldots+\frac{1}{n^{2}}\)
- Given: \(\ x_{1}, \ldots, x_{n}\) are positive numbers, prove the following: \(\ \frac{\left(x_{1}+\ldots+x_{n}\right)}{n} \geq\left(x_{1} \cdot \ldots \cdot x_{n}\right)^{\frac{1}{n}}\)
- \(\ n ! \geq 3^{n}\) for \(\ n=7,8,9, \ldots\)
Complete the following geometric induction proofs.
- Prove that side length of a quadrilateral is less than the sum of all its other side lengths.
- Prove that side length of a pentagon is less than the sum of all its other side lengths.
- Prove that it is possible to color all regions of a plane divided by several lines with two different colors, so that any two neighbor regions contain a different color.
Vocabulary
| Term | Definition |
|---|---|
| ! | The factorial of a whole number n is the product of the positive integers from 1 to n. The symbol "!" denotes factorial. n!=1⋅2⋅3⋅4...⋅(n−1)⋅n. |
| factorial | The factorial of a whole number n is the product of the positive integers from 1 to n. The symbol "!" denotes factorial. n!=1⋅2⋅3⋅4...⋅(n−1)⋅n. |
| induction | Induction is a method of mathematical proof typically used to establish that a given statement is true for all positive integers. |
| inequality | An inequality is a mathematical statement that relates expressions that are not necessarily equal by using an inequality symbol. The inequality symbols are <, >, ≤, ≥ and ≠. |
| Integer | The integers consist of all natural numbers, their opposites, and zero. Integers are numbers in the list ..., -3, -2, -1, 0, 1, 2, 3... |
| postulate | A postulate is a statement that is accepted as true without proof. |
| proof | A proof is a series of true statements leading to the acceptance of truth of a more complex statement. |