Skip to main content
K12 LibreTexts

7.3.2: Induction and Factors

  • Page ID
    14792
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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


    Examples

    Example 1

    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 2

    Prove that x - y is a factor of xn - yn 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 - y is a factor of xn - yn, then there exists a polynomial P such that P(x - y) = xn - yn.

    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 3
    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?

    Solution

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

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

    Example 4

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

    Solution

    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 ⇒ P(x - 1) = (xk - 1) for some polynomial Pxk + 1 - 1 = x(xk - 1) + (x - 1) = Px(x - 1) + (x - 1), which is divisible by x - 1

    Example 5

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

    Solution

    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.

    Example 6

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

    Solution

    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.


    Review

    1. Without adding, determine if 7 is 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 \(\ \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)\)
    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 \ldots\)

    Prove the following identities.

    1. \(\ 1^{2}+2^{2}+3^{2}+\ldots+n^{2}=\frac{n(n+1)(2 n+1)}{6}\)
    2. \(\ 1^{3}+2^{3}+3^{3}+\ldots+n^{3}=\frac{n^{2}(n+1)^{2}}{4}\)
    3. \(\ 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}\)
    4. \(\ 1 x \cdot 1 !+2 x \cdot 2 !+\ldots+n \cdot n !=(n+1) !-1\)
    5. \(\ n^{2} \frac{(n+1)^{2}}{4}=1^{3}+2^{3}+3^{3}+\ldots+n^{3}\)
    6. \(\ n(n+1) \frac{(2 n+1)}{6}=1^{2}+2^{2}+3^{2}+\ldots+n^{2}\)

    Prove the following divisibilities.

    1. Prove that \(\ n \frac{(n+1)}{2}\) is a factor of \(\ 1+2+3+\ldots+n\) for all positive integers \(\ n\)
    2. Prove that 3 is a factor of \(\ n^{3}+2 n\) 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}+\ldots+n^{3}\)

    Review (Answers)

    To see the Review answers, open this PDF file and look for section 7.7.


    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.

    This page titled 7.3.2: Induction and Factors is shared under a CK-12 license and was authored, remixed, and/or curated by CK-12 Foundation via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.

    CK-12 Foundation
    LICENSED UNDER
    CK-12 Foundation is licensed under CK-12 Curriculum Materials License
    • Was this article helpful?