# 7.3.3: Induction and Inequalities

- Page ID
- 14793

## 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* <

*and*

*b**<*

*b**, then*

*c**<*

*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* >

*, then*

*b**+*

*a**>*

*c**+*

*b**.*

*c*Multiplication property: if * a* >

*, and*

*b**> 0 then*

*c**>*

*ac**.*

*bc*## Examples

Prove that \(\ n ! \geq 2^{n}\) for \(\ n \geq 4\)

**Solution**

Step 1) The base case is * n* = 4: 4! = 24, 2

^{4}= 16. 24 ≥ 16 so the base case is true.

Step 2) Assume that * k*! ≥ 2

^{k}for some value of

*such that*

*k**≥ 4*

*k*Step 3) Show that (* k*+1)! ≥ 2

^{k+1}

(+1)! = k!(k+1)k |
Rewrite ( +1)! in terms of k !k |
---|---|

≥ 2^{k}( +1)k |
Use step 2 and the multiplication property. |

≥ 2^{k}(2) |
+1 ≥ 5 >2, so we can use the multiplication property again.k |

= 2^{k+1} |

Therefore * n*! ≥ 2

^{n}for

*≥ 4.*

*n*For what values of * x* is the inequality

*> x*

*x*^{2}true?

**Solution**

The inequality is true if * x* is a number between -1 and 1 but not 0.

Prove that 9^{n} - 1 is divisible by 8 for all positive integers * n*.

**Solution**

1. Base case: | If = 1, 9n^{n} - 1 = 9-1 = 8 = 8(1) |
---|---|

2. Inductive hypothesis: | Assume that 9^{k} - 1 is divisible by 8. |

3. Inductive step: | Show that 9^{k+1} - 1 is divisible by 8. |

9^{k} - 1 divisible by 8 ⇒ 8 = (9W^{k}-1) for some integer W |
---|

9^{k+1} - 1 = 9(9^{k} - 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. |