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.
Watch This
Khan Academy: Proof by Induction
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 4^{n}  1 for all positive integers n.
Solution:
Proof by induction:
 1. The base case: if n = 1, then 4^{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 n. For example, if n = 2, 4^{2}  1 = 16  1 = 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 B
Prove that x  y 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 x  y is a factor of x^{n}  y^{n}, then there exists a polynomial P such that P(x  y) = x^{n}  y^{n}.
Solution:
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 us 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}(x  y)  
=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.
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 \begin{align*}7 \times 7 = 49\end{align*}
 7 is a factor of 70, since \begin{align*}7 \times 10 = 70\end{align*}
 Therefore 7 is a factor of 119, since \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 9^{n}  1 is divisible by 8 for all positive integers n.
2) Prove that x^{n}  1 is divisible by x  1 for all positive integers n.
3) Prove that n^{2}  n is even for all positive integers n.
4) Prove that 5^{2n1} + 1 is divisible by 6 for all positive integers n.
Answers
1) Prove that 9^{n}  1 is divisible by 8 for all positive integers n.

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 \begin{align*}\Rightarrow\end{align*} 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
2) Prove that x^{n}  1 is divisible by x  1 for all positive integers n.

1. Base case: If n = 1, x^{k}  1 = x  1 = (x  1)(1) 2. Inductive hypothesis: Assume that x^{k}  1 is divisible by x  1 3. Inductive step: Show that x^{k+1}  1 is divisible by x  1.  x^{k}  1 divisible by x  1 \begin{align*}\Rightarrow\end{align*} P(x  1) = (x ^{k}  1) for some polynomial P
 x^{k + 1}  1 = x(x^{k}  1) + (x  1) = Px(x  1) + (x  1),which is divisible by x  1
3) Prove that n^{2}  n is even for all positive integers n

1. Base case: If n = 1, 1^{2}  1 = 1  1 = 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 = 2 M for some integer M
 (k + 1)^{2}  (k + 1) = k^{2} + 2k + 1  k  1 = k^{2}  k + 2k = 2M + 2k = 2(M + k) which is even because M + K is an integer.
4) Prove that 5^{2n  1} + 1 is divisible by 6 for all positive integers n.

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 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.
Explore More
 Without adding, determine if 7 a factor of 49 + 70
 Consider the sum \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?
 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 \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: \begin{align*}(x + \frac{1}{x})\end{align*}
 Prove the formula \begin{align*}n_{k + m} = n_{k1} u_m + n_k n_{m+1}\end{align*}for the sequence of Fibonacci numbers: \begin{align*}n_1 = 1, n_2 = 1, u_{k+1}= n_k + n_{k1}, k = 2, 3...\end{align*}
Prove the following identities.
 \begin{align*}1^2 + 2^2 + 3^2 + ... +n^2 =\frac{ n(n + 1)(2n + 1)}{6}\end{align*}
 \begin{align*}1^3 + 2^3 + 3^3 + ... + n^3 = \frac{n^2(n + 1)^2}{4}\end{align*}
 \begin{align*}1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + ... + n(n + 1)(n + 2) = \end{align*} \begin{align*}\frac{n(n + 1)(n + 2) (n + 3)}{4}\end{align*}
 \begin{align*}1 x \cdot 1! + 2 x \cdot 2! + ... + n \cdot n! = (n + 1)!  1\end{align*}
 \begin{align*}n^2 \frac{(n + 1)^2}{4} = 1^3 + 2^3 + 3^3 + ... + n^3\end{align*}
 \begin{align*}n (n + 1) \frac{(2n + 1)}{6} = 1^2 + 2^2 + 3^2 + ... + n^2\end{align*}
Prove the following divisibilities.
 Prove that \begin{align*}n \frac{(n+1)}{2}\end{align*} is a factor of \begin{align*}1 + 2 + 3 +... + n\end{align*} for all positive integers \begin{align*}n\end{align*}
 Prove that 3 is a factor of \begin{align*}n^3 + 2n\end{align*} for all positive integers n.
 Prove that \begin{align*}n^2 \frac{(n + 1)^2}{4}\end{align*} is a factor of \begin{align*}1^3 + 2^3 + 3^3 + ... + n^3\end{align*}
Answers for Explore More Problems
To view the Explore More answers, open this PDF file and look for section 7.7.