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

Proof by induction is common in mathematics, in this lesson we will use it to prove different kinds of hypothesis 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

Embedded Video:

- KhanAcademy: Proof by Induction

Guidance

In this lesson we will use induction to prove other kinds of statements. If you are not familiar with the concept of mathematical induction, it is strongly recommend that you first complete the lesson: "Inductive Proofs".

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

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 \times 7 = 49
7 is a factor of 70, since 7 \times 10 = 70
Therefore 7 is a factor of 119, since 49 + 70 = 119
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.

Vocabulary

A factor is a number or an expression that is multiplied with other factors to create a product.

A factorial refers to the product of the positive integers from 1 to some value n: n! = 1 × 2 × 3 × 4...× (n-1) × n

An inequality is a statement that two quantities are not equal.

A postulate is a statement that is accepted as true without proof.

Guided Practice

Questions

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.

Solutions

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

Practice

  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. 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 (x^n + \frac{1}{x^n}) is also an integer for any positive integer n if the following is an integer: (x + \frac{1}{x})
  6. 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...

Prove the following identities

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

Prove the following divisibilities:

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

Image Attributions

Description

Difficulty Level:

At Grade

Grades:

Date Created:

Nov 01, 2012

Last Modified:

Dec 12, 2013

We need you!

At the moment, we do not have exercises for Induction and Factors.

Files can only be attached to the latest version of Modality

Reviews

Please wait...
You need to be signed in to perform this action. Please sign-in and try again.
Please wait...
Image Detail
Sizes: Medium | Original
 
MAT.ALY.734.L.1

Original text