# 7.3.2: Induction and Factors

- Page ID
- 14792

## Induction and Factors

**Proof** by **induction** is common in mathematics. In this lesson we will use it to prove different kinds of hypotheses and to practice the use of the process in different situations. Specifically, we will be applying the principles of induction to prove various statements regarding factors and factorability.

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

*, and*

*b**is a factor of*

*a**, then*

*c**is a factor of the sum*

*a** b* +

*.*

*c*For example, the set of numbers * a* = 3,

*= 6, and*

*b**= 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 + 6 = 15, which we know is true because 3 × 5 = 15. We can prove that this property is true for all integers if we think about what the term*

*c**means. If*

*factor**is a factor of*

*a**, then there exists some*

*b***integer**

*such that*

*M**=*

*aM**. Similarly if*

*b**is a factor of*

*a**, then there exists some integer*

*c**such that*

*N**=*

*aN**. So we can write the sum*

*c**+*

*b**as*

*c**+*

*aM**. We know*

*aN* + b = c + aM = aN(a + M).N |
---|

Because we can write the sum as a product of * a *and another number,

*is a factor of the sum*

*a**+*

*b**.*

*c***Property 2**: If * a* is a factor of

*and*

*b**is a factor of*

*b**, then*

*c**is a factor of*

*a**.*

*c*We can prove this property in a similar manner. If * a* is a factor of

*, then there exists some integer*

*b**such that*

*M**=*

*aM**. If*

*b**is a factor of*

*b**, then there exists some integer*

*c**such that*

*N**=*

*bN**. We can write c in the following manner:*

*c** c* =

*= (*

*bN**)*

*aM**=*

*N**(*

*a**)*

*MN*Therefore * a* is a factor of

*because we can write*

*c**as the product of*

*c**and another integer,*

*a**.*

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

## Examples

Prove that 3 is a factor of 4^{n} - 1 for all positive integers * n*.

**Solution**

Proof by induction:

- The base case: if
= 1, then 4*n*^{n}- 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. For example, if*n*= 2, 4*n*^{2}- 1 = 16 - 1 = 15 = 5 × 3. - The inductive hypothesis: assume that 3 is a factor of 4
^{k}- 1. - 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 integersuch that 3*M*= 4*M*^{k}- 1. We can write 4^{k+1}- 1 in a manner that allows us to use the inductive hypothesis:4 ^{k+1}- 14(4 ^{k}-1) + 3Factor out 4, but add 3 in order to keep the value of 4 ^{k+1}-14(3 ) + 3*M*Substitute: 3 = 4*M*^{k}- 1Note 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

+ 1 term can also be used to prove statements about polynomials and factors.*k*

Prove that * x* -

*is a factor of*

*y*

*x*^{n}-

*y*^{n}for all positive integers

*.*

*n***Solution**

* Note:* Since we are talking about polynomials that are factorable now, not integers, then we say that if

*-*

*x**is a factor of*

*y*

*x*^{n}-

*y*^{n}, then there exists a polynomial

*such that*

*P**(*

*P**-*

*x**) =*

*y*

*x*^{n}-

*y*^{n}.

Proof by induction:

- The base case: If
= 1, we have*n**x*^{n}-*y*^{n}=-*x*, and*y*-*x*is a factor of itself, as*y*-*x*= 1(*y*-*x*).*y*As we did above, we can also check

= 2 in order to convince ourselves. If*n*= 2, we have*n**x*^{2}-*y*^{2}= (-*x*)(*y*+*x*), so*y*-*x*is clearly a factor.*y* - The inductive hypothesis: assume that
-*x*is a factor of*y**x*^{k}-*y*^{k}. - Show that
-*x*is a factor of*y**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 us to use the inductive hypothesis:

x^{k+1} - y^{k+1} |
---|

=x^{k+1} - xy^{k} + xy^{k} - y^{k+1} |

=(xx^{k} - y^{k}) + y^{k}( - x)y |

=(x(P - x)) + yy^{k}( - x)y |

=(Px - x) + yx y'^{k-1}( y-) |

Again, by property 1 above, this shows that * x* -

*is a factor of*

*y*

*x*^{k+1}- y

^{k+1}. Therefore we have shown that

*-*

*x**is a factor of*

*y*

*x*^{n}-

*y*^{n}for all positive integers

*.*

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

**Solution**

- Use Property 1 from the lesson:
*If a is a factor of b, and a is a factor of c, then a is a factor of the sum b + c.*7 is a factor of 70, since 7×10=70

Therefore 7 is a factor of 119, since 49+70=119

- This is a test of the converse of Property 1, which would be "If a number is a factor of the sum, then it is a factor of the factors of the sum"
7 is a factor of the sum: 77

7 is not a factor of 23 or 54

This tells us that the converse of the property is not necessarily true.

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

*.*

*n***Solution**

1. Base case: | If = 1, nx^{k} - 1 = x - 1 = (x - 1)(1) |
---|---|

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

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

*x*^{k} - 1 divisible by * x* - 1 ⇒

*(*

*P**- 1) = (*

*x*

*x*^{k}- 1) for some polynomial

*P*

*x*^{k + 1}- 1 =

*(*

*x*

*x*^{k}- 1) + (

*- 1) =*

*x**(*

*Px**- 1) + (*

*x**- 1), which is divisible by*

*x**- 1*

*x*Prove that *n*^{2} - n is even for all positive integers * n*.

**Solution**

1. Base case: | If = 1, 1n^{2} - 1 = 1 - 1 = 0 = 2 × 0 |
---|---|

2. Inductive hypothesis: | Assume that k^{2} - is evenk |

3. Inductive step: | Show that ( + 1)k^{2} - ( + 1) is even.k |

If *k*^{2} - * k* is even, then

*k*^{2}-

*= 2*

*k**for some integer*

*M**(*

*M**+ 1)*

*k*^{2}- (

*+ 1) =*

*k*

*k*^{2}+ 2

*+ 1 -*

*k**- 1 =*

*k*

*k*^{2}-

*+ 2*

*k**= 2*

*k**+ 2*

*M**= 2(*

*k**+*

*M**) which is even because*

*k**+*

*M**is an integer.*

*K*Prove that 5^{2n-1} + 1 is divisible by 6 for all positive integers * n*.

**Solution**

1. Base case: | If = 1, 5n^{1} + 1 = 5 + 1 = 6 = 6(1) |
---|---|

2. Inductive hypothesis: | Assume that 5^{2k-1} + 1 is divisible by 6. |

3. Inductive step: | Show that 5^{2(k + 1) - 1} + 1 is divisible by 6. |

If 5^{2k - 1} + 1 is divisible by 6, then 5^{2k - 1} + 1 = 6M for some integer * M*. 5

^{2(k + 1) - 1}+ 1 = 5

^{2k + 1}+ 1 = 5

^{2}(5

^{2k - 1}+ 1) - 24 = 5

^{2}(6M) - 24 which is divisible by 6.

## Review

- Without adding, determine if 7 is 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?
- Prove that any positive integer n > 1 a) is prime or, b) can be represented as a product of prime factors.
- Found within set "J" are all positive integers, from the number 1 to 2n. Prove that there are two numbers, one that is a factor of another, from any (n = 1) numbers chosen from set "J"
- Prove that \(\ \left(x^{n}+\frac{1}{x^{n}}\right)\) is also an integer for any positive integer n if the following is an integer: \(\ \left(x+\frac{1}{x}\right)\)
- Prove the formula \(\ n_{k+m}=n_{k-1} u_{m}+n_{k} n_{m+1}\) for the sequence of Fibonacci numbers: \(\ n_{1}=1, n_{2}=1, u_{k+1}=n_{k}+n_{k-1}, k=2,3 \ldots\)

Prove the following identities.

- \(\ 1^{2}+2^{2}+3^{2}+\ldots+n^{2}=\frac{n(n+1)(2 n+1)}{6}\)
- \(\ 1^{3}+2^{3}+3^{3}+\ldots+n^{3}=\frac{n^{2}(n+1)^{2}}{4}\)
- \(\ 1 \cdot 2 \cdot 3+2 \cdot 3 \cdot 4+\ldots+n(n+1)(n+2)=\frac{n(n+1)(n+2)(n+3)}{4}\)
- \(\ 1 x \cdot 1 !+2 x \cdot 2 !+\ldots+n \cdot n !=(n+1) !-1\)
- \(\ n^{2} \frac{(n+1)^{2}}{4}=1^{3}+2^{3}+3^{3}+\ldots+n^{3}\)
- \(\ n(n+1) \frac{(2 n+1)}{6}=1^{2}+2^{2}+3^{2}+\ldots+n^{2}\)

Prove the following divisibilities.

- Prove that \(\ n \frac{(n+1)}{2}\) is a factor of \(\ 1+2+3+\ldots+n\) for all positive integers \(\ n\)
- Prove that 3 is a factor of \(\ n^{3}+2 n\) for all positive integers \(\ n\).
- Prove that \(\ n^{2} \frac{(n+1)^{2}}{4}\) is a factor of \(\ 1^{3}+2^{3}+3^{3}+\ldots+n^{3}\)

## Vocabulary

Term | Definition |
---|---|

factor |
Factors are the numbers being multiplied to equal a product. To factor means to rewrite a mathematical expression as a product of factors. |

induction |
Induction is a method of mathematical proof typically used to establish that a given statement is true for all positive integers. |

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

proof |
A proof is a series of true statements leading to the acceptance of truth of a more complex statement. |