<meta http-equiv="refresh" content="1; url=/nojavascript/"> Induction and Inequalities | CK-12 Foundation
Dismiss
Skip Navigation
You are reading an older version of this FlexBook® textbook: CK-12 Math Analysis Concepts Go to the latest version.

7.8: Induction and Inequalities

Created by: CK-12

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.

Watch This

Embedded Video:

- James Sousa: Mathematical Induction

Guidance

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 unlike the factor properties we used above, 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 .

Example A

Prove that n ! ≥ 2 n for n ≥ 4

Solution

1. The base case is n = 4: 4! = 24, 2 4 = 16. 24 ≥ 16 so the base case is true.
2. Assume that k ! ≥ 2 k for some value of k such that k ≥ 4
3. Show that ( k +1)! ≥ 2 k+1
( k +1)! = k !( k +1) Rewrite ( k +1)! in terms of k !
≥ 2 k ( k +1) Use step 2 and the multiplication property.
≥ 2 k (2) k +1 ≥ 5 >2, so we can use the multiplication property again.
= 2 k+1

Therefore n ! ≥ 2 n for n ≥ 4.

Example B

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.

Example C

Prove that 9 n - 1 is divisible by 8 for all positive integers n .

Solution

1. Base case: If n = 1, 9 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 \Rightarrow 8 W = (9 k -1) for some integer W
9 k+1 - 1 = 9(9 k - 1) + 8 = 9(8W) + 8,which is divisible by 8

Vocabulary

A factor is a number or an expression that is multiplied with other factors to create a product.

Factorial refers to the product of the positive integers from 1 to some value n :

n ! = 1 × 2 × 3 × 4...× ( n -1) × n

An inequality is a statement that two quantities are not equal.

A postulate is a statement that is accepted as true without proof.

Guided Practice

1) Prove that 2^n < n! for all positive integers n where n \geq 4

2) Prove that n^2 < 3^n for all integers n > 2

3) Prove that 2 n + 1 < 2 n for all integers n > 3

Solutions

1) 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 ..... If k \geq 4 then this is true
2^k \cdot 2 < 2^k (k + 1) ... 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

2) 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
2k < k^2 and 1 < k^2 ..... assuming 2 < k as specified in the question
2k + 1 < 2k^2 ..... combine the two statements above
k^2 + 2k + 1< 3k^2 ..... add k^2 to both sides
(k + 1)^2 < 3k^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

3) Prove that 2 n + 1 < 2 n for all integers n > 3

1. Base case: If n = 3, 2(3) + 1 = 7, 2 3 = 8 : 7 < 8, so the base case is true.
2. Inductive hypothesis: Assume that 2 k + 1 < 2 k for k > 3
3. Inductive step: Show that 2( k + 1) + 1 < 2 k + 1
2( k + 1) + 1 = 2 k + 2 + 1 = (2k + 1) + 2 < 2 k + 2 < 2 k + 2 k = 2 (2 k ) = 2 k + 1

Practice

  1. 5^k<(k+5)!
  2. 1^k < (k + 1)!
  3. 4^k< (k  4)!
  4. 2^k<(k + 2)!
  5. For what values of x is the inequality x > x 2 true?
  6. Prove that 3 n > n 2 for all positive integers n .

Prove the following inequalities

  1. \frac{1}{n + 1} + \frac{1}{n+2} + \frac{1}{n + 3} + ... + \frac{1}{2n}> \frac{13}{24}(n > 1)
  2. 2^n \geq n^2 for n = 4, 5, 6,...
  3. \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + ... +\frac{1}{n^2}
  4. Given: x_1, ..., x_n are positive numbers, prove the following: \frac{(x_1+ ...+ x_n)}{n} \geq (x_1 \cdot ...\cdot x_n)^{\frac{1}{n}}
  5. n! \geq 3^n for n = 7, 8, 9, ....

Geometric Induction

  1. Prove that side length of a quadrilateral is less than the sum of all its other side lengths.
  2. Prove that side length of a pentagon is less than the sum of all its other side lengths.
  3. Prove that a square may be divided into any number of smaller squares greater than 5, without any remaining squares.
  4. 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.

Image Attributions

Description

Difficulty Level:

At Grade

Grades:

Date Created:

Nov 01, 2012

Last Modified:

Dec 08, 2014

We need you!

At the moment, we do not have exercises for Induction and Inequalities.

Files can only be attached to the latest version of Modality

Reviews

Please wait...
Please wait...
Image Detail
Sizes: Medium | Original
 
MAT.ALY.736.L.1

Original text