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

7.4: Mathematical Induction, Factors, and Inequalities

Created by: CK-12
 0  0  0

Learning objectives

  • Use induction to prove statements involving factors.
  • Use induction to prove statements involving inequalities.

Introduction

In the previous lesson we introduced mathematical induction, a method that allows us to prove that a given statement is true for all positive integers. The proofs in the previous lesson focused on sums. For example, we proved a formula for the sum of the first n positive integers. In this lesson we will use induction to prove other kinds of statements. First we will prove statements about factors, and then we will prove statements about inequalities.

First we discuss several important properties of integers that will be used to prove statements about factors.

Integers and Factors

There are two properties of integers and their factors that will be useful for the proofs in this lesson.

Property 1: If a is a factor of b, and a is a factor of c, then a is a factor of the sum b+c.

For example, the set of numbers a = 3, b = 6, and c = 9 satisfies the hypothesis because 3 is a factor of 6 and 3 is a factor of 9. Property 1 states that therefore 3 is a factor of 9 + 3 =12, which we know is true because 3 × 4=12 . We can prove that this property is true for all integers if we think about what the term factor means. If a is a factor of b, then there exists some integer M such that aM=b. Similarly if a is a factor of c, then there exists some integer N such that aN=c. So we can write the sum b+c as aM+aN. We know
b + c=aM + aN=a(M + N).
Because we can write the sum as a product of a and another number, a is a factor of the sum b + c.

Property 2: If a is a factor of b and b is a factor of c, then a is a factor of c.

We can prove this property in a similar manner. If a is a factor of b, then there exists some integer M such that aM=b. If b is a factor of c, then there exists some integer N such that bN=c. We can write c in the following manner:
c=bN=(aM)N=a(MN)
Therefore a is a factor of c because we can write c as the product of a and another integer, MN.

As noted above, these properties of integers are useful for proving statements about integers and factors via induction.

Induction and factors

Here we will use induction to prove statements about factors. The first example focuses on integers. The second focuses on polynomials.

Example 1: Prove that 3 is a factor of 4n-1 for all positive integers n.

Proof by induction:

1. The base case: if n = 1, then 4n-1=4-1=3. 3 is a factor of itself because 3 × 1=3 .
If the base case does not convince you, you can always test out additional values of n. For example, if n = 2, 42-1=16-1=15=5 × 3.
2. The inductive hypothesis: assume that 3 is a factor of 4k-1.
3. The inductive step: show that 3 is a factor of 4k+1-1.
If 3 is a factor of 4k-1, then there exists some integer M such that 3M=4k-1. We can write 4k+1-1 in a manner that allows us to use the inductive hypothesis:
4k+1-1
4(4k-1)+3 Factor out 4, but add 3 in order to keep the value of 4k+1-1
4(3M)+3 Substitute: 3M=4k-1
Note that the substitution is the same as using property 2 above: if 3 is a factor of 4k-1 , then 3 is a factor of 4(4k-1). Using the substitution simply makes the fact a bit more obvious.
This last step proves that 3 is a factor of 4k+1-1 , by property 1 above.

The technique of rewriting the k+1 term can also be used to prove statements about polynomials and factors.

Example 2: Prove that x-y is a factor of xn-yn for all positive integers n.

Note: Since we are talking about polynomials that are factorable now, not integers, then we say that if x-y is a factor of xn-yn, then there exists a polynomial P such that P(x-y)=xn-yn.

Proof by induction:

1. The base case: If n = 1, we have xn-yn=x - y , and x - y is a factor of itself, as x - y=1(x - y).
As we did above, we can also check n = 2 in order to convince ourselves. If n = 2, we have x2-y2=(x - y)(x + y), so x - y is clearly a factor.
2. The inductive hypothesis: assume that x - y is a factor of xk-yk.
3. Show that x - y is a factor of xk+1-yk+1.
From the inductive step, we know that there is some polynomial P such that P(x - y)=xk-yk. We can rewrite xk+1-yk+1 in a manner that allows use to use the inductive hypothesis:
xk+1-yk+1
=xk+1-xyk + xyk -yk+1
=x(xk-yk) + yk(x-y)
=x(P(x - y)) + yk(x - y)
=Px(x - y)+y'k-1(x - y)
Again, by property 1 above, this shows that x - y is a factor of xk+1-yk+1. Therefore we have shown that x - y is a factor of xn-yn for all positive integers n.

The two proofs here have established properties of integers and polynomials involving factors. Now we will use induction to prove several statements about 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 ab.

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.

We will use these properties in the proof below.

Induction and Inequalities

Example 3: Prove that n! ≥ 2n for n ≥ 4

Proof by induction:

1. The base case is n = 4:4!=24, 24=16. 24 ≥ 16 so the base case is true.
2. Assume that k! ≥ 2k for some value of k such that k ≥ 4
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.

Lesson Summary

In this lesson we have extended the method of mathematical induction beyond proofs involving sums. Here we have proven statements about factors, and statements about inequalities. Induction is the method of choice for such proofs because we need to prove that a given statement is true for all positive integers. However, induction is only one method of proof. Many mathematical relationships can be proven without induction.

Points to Consider

  1. How are the statements proven in this lesson different from the ones proven in the previous lesson?
  2. Why do we limit the values of n to the natural numbers?
  3. How can we prove relationships without induction?

Review Questions

  1. Without adding, determine if 7 a factor of 49+70.
  2. Consider the sum 23+54=77. Is 7 a factor of 77? What does this tell you about the first factor property in the lesson?
  3. For what values of x is the inequality x > x2 true?
  4. Evaluate each expression: a.4!+3! b.\frac {6!}{5!}
  5. Prove that 9n-1 is divisible by 8 for all positive integers n.
  6. Prove that xn-1 is divisible by x-1 for all positive integers n.
  7. Prove that n2-n is even for all positive integers n.
  8. Prove that 52n-1+1 is divisible by 6 for all positive integers n.
  9. Prove that 2n+1 < 2n for all integers n > 3
  10. Prove that 3n > n2 for all positive integers n.

Review Answer

  1. 7 is a factor of the sum, as it is a factor of 49 and a factor of 70.
  2. 7 is a factor of 77, but it is not a factor of 23 or 54. This tells us that the converse of the property is not necessarily true.
  3. The inequality is true if x is a number between -1 and 1 but not 0.
  4. a. 30 b. 6
  5. 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 \Rightarrow 8W = (9k-1) for some integer W
    9k+1-1=9(9k-1)+8=9(8W)+8,which is divisible by 8
  6. 1. Base case: If n = 1,xk-1=x-1=(x-1)(1)
    2. Inductive hypothesis: Assume that xk-1 is divisible by x-1
    3. Inductive step: Show that xk+1-1 is divisible by x-1.

    xk-1 divisible by x-1 \Rightarrow P(x-1)=(x k-1) for some polynomial P xk+1-1=x(x k-1)+(x-1)=Px(x-1)+(x-1),which is divisible by x-1

  7. 1. Base case: If n = 1,12-1=1-1=0=2×0
    2. Inductive hypothesis: Assume that k2-k is even
    3. Inductive step: Show that (k+1)2-(k+1) is even.

    If k2-k is even, then k2-k=2M for some integer M (k+1)2-(k+1)=k2+2k+1-k-1=k2-k+2k=2M+2k=2(M+k),which is even because M+K is an integer.

  8. 1. Base case: If n = 1,51+1=5+1=6=6(1)
    2. Inductive hypothesis: Assume that 52k-1+1 is divisible by 6.
    3. Inductive step: Show that 52(k+1)-1+1</math> is divisible by 6.

    If 52k-1+1 is divisible by 6, then 52k-1+1 =6M for some integer M. 52(k+1)-1}+1 = 52k+1+1= 52(52k-1+1)-24=52(6M)-24 which is divisible by 6.

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

    2(k+1)+1 =2k+2+1=(2k+1)+2<2k +2<2k+2k=2(2k)=2k+1

  10. 1. Base case: If n = 1, 31 = 3 and 12 =1. 3 > 1 so the base case is true.
    2. Inductive hypothesis: Assume that 3k > k2
    3. Inductive step: Show that 3k+1 > (k+1)2

    (k+1)2 = k2+2k+1<3k+2k+1<3k+2k<3k+3k<3 × 3k=3k+1

Vocabulary

Factor
A factor is a number or an expression that is multiplied with other factors to create a product.
Factorial
Factorial refers to the product of the positive integers from 1 to some value n:
n!=1 × 2 × 3 × 4...× (n-1) × n
Inequality
An inequality is a statement that two quantities are not equal.
Postulate
A postulate is a statement that is accepted as true without proof.

Image Attributions

Files can only be attached to the latest version of None

Reviews

Please wait...
Please wait...
Image Detail
Sizes: Medium | Original
 
CK.MAT.ENG.SE.1.Math-Analysis.7.4
ShareThis Copy and Paste

Original text