<img src="https://d5nxst8fruw4z.cloudfront.net/atrk.gif?account=iA1Pi1a8Dy00ym" style="display:none" height="1" width="1" alt="" />

# Induction and Factors

## Proving divisibility using properties of integers and inductive proofs.

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

### Guidance

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

#### Example A

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

Solution:

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 B

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.

Solution:

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

#### Example C

a) Without adding, determine if 7 a factor of 49 + 70.
b) 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:

a) 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 49, since 7×7=49\begin{align*}7 \times 7 = 49\end{align*}
7 is a factor of 70, since 7×10=70\begin{align*}7 \times 10 = 70\end{align*}
Therefore 7 is a factor of 119, since 49+70=119\begin{align*}49 + 70 = 119\end{align*}
b) 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.

-->

### Guided Practice

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

2) Prove that xn - 1 is divisible by x - 1 for all positive integers n.

3) Prove that n2 - n is even for all positive integers n.

4) Prove that 52n-1 + 1 is divisible by 6 for all positive integers n.

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

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 \begin{align*}\Rightarrow\end{align*} 8W = (9k - 1) for some integer W
9k + 1 - 1 = 9 (9k - 1) + 8 = 9 (8W) + 8, which is divisible by 8

2) Prove that xn - 1 is divisible by x - 1 for all positive integers n.

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 \begin{align*}\Rightarrow\end{align*} P(x - 1) = (x k - 1) for some polynomial P
xk + 1 - 1 = x(xk - 1) + (x - 1) = Px(x - 1) + (x - 1),which is divisible by x - 1

3) Prove that n2 - n is even for all positive integers n

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 = 2 M 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.

4) Prove that 52n - 1 + 1 is divisible by 6 for all positive integers n.

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

### Explore More

1. Without adding, determine if 7 a factor of 49 + 70
2. Consider the sum 23+54=77\begin{align*}23 + 54 = 77\end{align*} Is 7 a factor of 77? What does this tell you about the first factor property in the lesson?
3. Prove that any positive integer n > 1 a) is prime or, b) can be represented as a product of prime factors.
4. 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"
5. Prove that (xn+1xn)\begin{align*}(x^n + \frac{1}{x^n})\end{align*} is also an integer for any positive integer n if the following is an integer: (x+1x)\begin{align*}(x + \frac{1}{x})\end{align*}
6. Prove the formula nk+m=nk1um+nknm+1\begin{align*}n_{k + m} = n_{k-1} u_m + n_k n_{m+1}\end{align*}for the sequence of Fibonacci numbers: n1=1,n2=1,uk+1=nk+nk1,k=2,3...\begin{align*}n_1 = 1, n_2 = 1, u_{k+1}= n_k + n_{k-1}, k = 2, 3...\end{align*}

Prove the following identities.

1. 12+22+32+...+n2=n(n+1)(2n+1)6\begin{align*}1^2 + 2^2 + 3^2 + ... +n^2 =\frac{ n(n + 1)(2n + 1)}{6}\end{align*}
2. 13+23+33+...+n3=n2(n+1)24\begin{align*}1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^2(n + 1)^2}{4}\end{align*}
3. 123+234+...+n(n+1)(n+2)=\begin{align*}1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + ... + n(n + 1)(n + 2) = \end{align*} n(n+1)(n+2)(n+3)4\begin{align*}\frac{n(n + 1)(n + 2) (n + 3)}{4}\end{align*}
4. 1x1!+2x2!+...+nn!=(n+1)!1\begin{align*}1 x \cdot 1! + 2 x \cdot 2! + ... + n \cdot n! = (n + 1)! - 1\end{align*}
5. n2(n+1)24=13+23+33+...+n3\begin{align*}n^2 \frac{(n + 1)^2}{4} = 1^3 + 2^3 + 3^3 + ... + n^3\end{align*}
6. n(n+1)(2n+1)6=12+22+32+...+n2\begin{align*}n (n + 1) \frac{(2n + 1)}{6} = 1^2 + 2^2 + 3^2 + ... + n^2\end{align*}

Prove the following divisibilities.

1. Prove that n(n+1)2\begin{align*}n \frac{(n+1)}{2}\end{align*} is a factor of 1+2+3+...+n\begin{align*}1 + 2 + 3 +... + n\end{align*} for all positive integers n\begin{align*}n\end{align*}
2. Prove that 3 is a factor of n3+2n\begin{align*}n^3 + 2n\end{align*} for all positive integers n.
3. Prove that n2(n+1)24\begin{align*}n^2 \frac{(n + 1)^2}{4}\end{align*} is a factor of 13+23+33+...+n3\begin{align*}1^3 + 2^3 + 3^3 + ... + n^3\end{align*}

### Vocabulary Language: English

factor

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

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

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

proof

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