7.4: Mathematical Induction, Factors, and Inequalities
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 4^{n}1 for all positive integers n.
Proof by induction:
 1. The base case: if n = 1, then 4^{n}1=41=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, 4^{2}1=161=15=5 × 3.
 2. The inductive hypothesis: assume that 3 is a factor of 4^{k}1.
 3. The inductive step: show that 3 is a factor of 4^{k+1}1.

 If 3 is a factor of 4^{k}1, then there exists some integer M such that 3M=4^{k}1. We can write 4^{k+1}1 in a manner that allows us to use the inductive hypothesis:
4^{k+1}1  

4(4^{k}1)+3  Factor out 4, but add 3 in order to keep the value of 4^{k+1}1  
4(3M)+3  Substitute: 3M=4^{k}1 

 Note that the substitution is the same as using property 2 above: if 3 is a factor of 4^{k}1 , then 3 is a factor of 4(4^{k}1). Using the substitution simply makes the fact a bit more obvious.

 This last step proves that 3 is a factor of 4^{k+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 xy is a factor of x^{n}y^{n} for all positive integers n.
 Note: Since we are talking about polynomials that are factorable now, not integers, then we say that if xy is a factor of x^{n}y^{n}, then there exists a polynomial P such that P(xy)=x^{n}y^{n}.
Proof by induction:
 1. The base case: If n = 1, we have x^{n}y^{n}=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 x^{2}y^{2}=(x  y)(x + y), so x  y is clearly a factor.
 2. The inductive hypothesis: assume that x  y is a factor of x^{k}y^{k}.
 3. Show that x  y is a factor of x^{k+1}y^{k+1}.

 From the inductive step, we know that there is some polynomial P such that P(x  y)=x^{k}y^{k}. We can rewrite x^{k+1}y^{k+1} in a manner that allows use to use the inductive hypothesis:
x^{k+1}y^{k+1}  

=x^{k+1}xy^{k} + xy^{k} y^{k+1}  
=x(x^{k}y^{k}) + y^{k}(xy)  
=x(P(x  y)) + y^{k}(x  y)  
=Px(x  y)+y'^{k1}(x  y) 

 Again, by property 1 above, this shows that x  y is a factor of x^{k+1}y^{k+1}. Therefore we have shown that x  y is a factor of x^{n}y^{n} 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 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.
We will use these properties in the proof below.
Induction and Inequalities
Example 3: Prove that n! ≥ 2^{n} for n ≥ 4
Proof by induction:
 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.
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
 How are the statements proven in this lesson different from the ones proven in the previous lesson?
 Why do we limit the values of n to the natural numbers?
 How can we prove relationships without induction?
Review Questions
 Without adding, determine if 7 a factor of 49+70.
 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?
 For what values of x is the inequality x > x^{2} true?
 Evaluate each expression: a.4!+3! b.
 Prove that 9^{n}1 is divisible by 8 for all positive integers n.
 Prove that x^{n}1 is divisible by x1 for all positive integers n.
 Prove that n^{2}n is even for all positive integers n.
 Prove that 5^{2n1}+1 is divisible by 6 for all positive integers n.
 Prove that 2n+1 < 2^{n} for all integers n > 3
 Prove that 3^{n} > n^{2} for all positive integers n.
Review Answer
 7 is a factor of the sum, as it is a factor of 49 and a factor of 70.
 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.
 The inequality is true if x is a number between 1 and 1 but not 0.
 a. 30 b. 6

1. Base case: If n = 1,9^{n}1=91=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 8W = (9^{k}1) for some integer W 9^{k+1}1=9(9^{k}1)+8=9(8W)+8,which is divisible by 8 
1. Base case: If n = 1,x^{k}1=x1=(x1)(1) 2. Inductive hypothesis: Assume that x^{k}1 is divisible by x1 3. Inductive step: Show that x^{k+1}1 is divisible by x1. x^{k}1 divisible by x1 P(x1)=(x ^{k}1) for some polynomial P x^{k+1}1=x(x ^{k}1)+(x1)=Px(x1)+(x1),which is divisible by x1

1. Base case: If n = 1,1^{2}1=11=0=2×0 2. Inductive hypothesis: Assume that k^{2}k is even 3. Inductive step: Show that (k+1)^{2}(k+1) is even. If k^{2}k is even, then k^{2}k=2M for some integer M (k+1)^{2}(k+1)=k^{2}+2k+1k1=k^{2}k+2k=2M+2k=2(M+k),which is even because M+K is an integer.

1. Base case: If n = 1,5^{1}+1=5+1=6=6(1) 2. Inductive hypothesis: Assume that 5^{2k1}+1 is divisible by 6. 3. Inductive step: Show that 5^{2(k+1)1}+1</math> is divisible by 6. If 5^{2k1}+1 is divisible by 6, then 5^{2k1}+1 =6M for some integer M. 5^{2(k+1)1}}+1 = 5^{2k+1}+1= 5^{2}(5^{2k1}+1)24=5^{2}(6M)24 which is divisible by 6.

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 2k+1< 2^{k} for k > 3 3. Inductive step: Show that 2(k+1)+1 < 2^{k+1} 2(k+1)+1 =2k+2+1=(2k+1)+2<2^{k} +2<2^{k}+2^{k}=2(2^{k})=2^{k+1}

1. Base case: If n = 1, 3^{1} = 3 and 1^{2} =1. 3 > 1 so the base case is true. 2. Inductive hypothesis: Assume that 3^{k} > k^{2} 3. Inductive step: Show that 3^{k+1} > (k+1)^{2} (k+1)^{2} = k^{2}+2k+1<3^{k}+2k+1<3^{k}+2^{k}<3^{k}+3^{k}<3 × 3^{k}=3^{k+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...× (n1) × 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.