← Proof by Mathematical Induction › Induction for Divisibility and Inequalities › Solutions

Induction for Divisibility and Inequalities — Full Worked Solutions

1. Verify the base case and inductive hypothesis for each divisibility statement. Fluency

   ▶ Show Answer

   (a) 3 | (4ⁿ − 1):

   Base case n = 1: 4¹ − 1 = 3. Since 3 = 3 × 1, we have 3 | 3. ✓

   Inductive hypothesis: Assume 3 | (4^k − 1) for some integer k ≥ 1, i.e. 4^k − 1 = 3m for some integer m.

   (b) 5 | (6ⁿ − 1):

   Base case n = 1: 6¹ − 1 = 5. Since 5 = 5 × 1, we have 5 | 5. ✓

   Inductive hypothesis: Assume 5 | (6^k − 1) for some integer k ≥ 1, i.e. 6^k − 1 = 5m for some integer m.

   (c) 7 | (8ⁿ − 1):

   Base case n = 1: 8¹ − 1 = 7. Since 7 = 7 × 1, we have 7 | 7. ✓

   Inductive hypothesis: Assume 7 | (8^k − 1) for some integer k ≥ 1, i.e. 8^k − 1 = 7m for some integer m.

2. Complete the inductive step. Fluency

   ▶ Show Answer

   We need to show that 5 | (6^k+1 − 1), given that 6^k − 1 = 5m.

   6^k+1 − 1 = 6 × 6^k − 1

   = 6(6^k − 1) + 5     [add and subtract 6 to isolate f(k)]

   = 6 × 5m + 5     [by the inductive hypothesis, 6^k − 1 = 5m]

   = 5(6m + 1).

   Since 6m + 1 is an integer, 5 | (6^k+1 − 1). ✓

   Conclusion: By mathematical induction, 5 | (6ⁿ − 1) for all integers n ≥ 1.

3. Prove 3 | (n³ − n) for all integers n ≥ 1. Fluency

   ▶ Show Answer

   Claim: P(n): 3 | (n³ − n) for all integers n ≥ 1.

   Base case n = 1: 1³ − 1 = 0. Since 0 = 3 × 0, we have 3 | 0. ✓

   Inductive hypothesis: Assume 3 | (k³ − k) for some integer k ≥ 1, i.e. k³ − k = 3m.

   Inductive step: We must show 3 | ((k+1)³ − (k+1)).

   (k+1)³ − (k+1) = k³ + 3k² + 3k + 1 − k − 1

   = (k³ − k) + 3k² + 3k

   = (k³ − k) + 3k(k + 1)

   = 3m + 3k(k+1)     [by the inductive hypothesis]

   = 3(m + k(k+1)).

   Since m + k(k+1) is an integer, 3 | ((k+1)³ − (k+1)). ✓

   Conclusion: By the principle of mathematical induction, 3 | (n³ − n) for all integers n ≥ 1.

4. Verify the base case for each inequality. Fluency

   ▶ Show Answer

   (a) n! > 2ⁿ for n ≥ 4:

   Base case n = 4: LHS = 4! = 24. RHS = 2⁴ = 16. Since 24 > 16, the inequality holds. ✓

   (b) 2ⁿ > n² for n ≥ 5:

   Base case n = 5: LHS = 2⁵ = 32. RHS = 5² = 25. Since 32 > 25, the inequality holds. ✓

   (Note: for n = 4, 2⁴ = 16 = 4² — equality, not strict inequality. So n = 4 is not a valid base case for a strict inequality.)

   (c) n² > 2n + 1 for n ≥ 3:

   Base case n = 3: LHS = 3² = 9. RHS = 2(3) + 1 = 7. Since 9 > 7, the inequality holds. ✓

5. Prove 6 | (n³ − n) for all integers n ≥ 1. Understanding

   ▶ Show Answer

   Claim: P(n): 6 | (n³ − n) for all integers n ≥ 1.

   Base case n = 1: 1³ − 1 = 0. 6 | 0. ✓

   Inductive hypothesis: Assume 6 | (k³ − k) for some integer k ≥ 1, i.e. k³ − k = 6m.

   Inductive step: Consider (k+1)³ − (k+1).

   (k+1)³ − (k+1) = k³ + 3k² + 3k + 1 − k − 1

   = (k³ − k) + 3k² + 3k

   = (k³ − k) + 3k(k + 1).

   By the inductive hypothesis, 6 | (k³ − k).

   Now consider 3k(k+1): k and k+1 are consecutive integers, so one of them must be even. Therefore k(k+1) = 2t for some integer t, giving 3k(k+1) = 6t, which is divisible by 6.

   Therefore (k+1)³ − (k+1) = 6m + 6t = 6(m + t), and since m + t is an integer, 6 | ((k+1)³ − (k+1)). ✓

   Conclusion: By the principle of mathematical induction, 6 | (n³ − n) for all integers n ≥ 1.

6. Prove n! > 2ⁿ for all integers n ≥ 4. Understanding

   ▶ Show Answer

   Claim: P(n): n! > 2ⁿ for all integers n ≥ 4.

   Base case n = 4: 4! = 24 and 2⁴ = 16. Since 24 > 16, P(4) is true. ✓

   Inductive hypothesis: Assume k! > 2^k for some integer k ≥ 4.

   Inductive step: We must show (k+1)! > 2^k+1.

   (k+1)! = (k+1) × k!

   > (k+1) × 2^k     [by the inductive hypothesis, since k+1 > 0]

   > 2 × 2^k     [since k ≥ 4 implies k+1 ≥ 5 > 2]

   = 2^k+1.

   Therefore (k+1)! > 2^k+1. ✓

   Conclusion: By the principle of mathematical induction, n! > 2ⁿ for all integers n ≥ 4.

7. Prove 2ⁿ > n² for all integers n ≥ 5. Understanding

   ▶ Show Answer

   Claim: P(n): 2ⁿ > n² for all integers n ≥ 5.

   Base case n = 5: 2⁵ = 32 and 5² = 25. Since 32 > 25, P(5) is true. ✓

   Inductive hypothesis: Assume 2^k > k² for some integer k ≥ 5.

   Inductive step: We must show 2^k+1 > (k+1)².

   2^k+1 = 2 × 2^k

   > 2k²     [by the inductive hypothesis]

   We now show 2k² ≥ (k+1)² = k² + 2k + 1.

   This requires k² − 2k − 1 ≥ 0, i.e. (k−1)² ≥ 2.

   Since k ≥ 5, we have k − 1 ≥ 4, so (k−1)² ≥ 16 ≥ 2. ✓

   Therefore 2^k+1 > 2k² ≥ (k+1)². ✓

   Conclusion: By the principle of mathematical induction, 2ⁿ > n² for all integers n ≥ 5.

8. Prove 8 | (9ⁿ − 1) for all integers n ≥ 1. Understanding

   ▶ Show Answer

   Claim: P(n): 8 | (9ⁿ − 1) for all integers n ≥ 1.

   Base case n = 1: 9¹ − 1 = 8. Since 8 = 8 × 1, we have 8 | 8. ✓

   Inductive hypothesis: Assume 8 | (9^k − 1) for some integer k ≥ 1, i.e. 9^k − 1 = 8m.

   Inductive step: We must show 8 | (9^k+1 − 1).

   9^k+1 − 1 = 9 × 9^k − 1

   = 9(9^k − 1) + 8

   = 9(8m) + 8     [by the inductive hypothesis]

   = 72m + 8

   = 8(9m + 1).

   Since 9m + 1 is an integer, 8 | (9^k+1 − 1). ✓

   Conclusion: By the principle of mathematical induction, 8 | (9ⁿ − 1) for all integers n ≥ 1.

9. Prove 3 | (n³ + 2n) for all integers n ≥ 1. Problem Solving

   ▶ Show Answer

   Claim: P(n): 3 | (n³ + 2n) for all integers n ≥ 1.

   Base case n = 1: 1³ + 2(1) = 1 + 2 = 3. Since 3 = 3 × 1, we have 3 | 3. ✓

   Inductive hypothesis: Assume 3 | (k³ + 2k) for some integer k ≥ 1, i.e. k³ + 2k = 3m.

   Inductive step: We must show 3 | ((k+1)³ + 2(k+1)).

   (k+1)³ + 2(k+1) = k³ + 3k² + 3k + 1 + 2k + 2

   = (k³ + 2k) + 3k² + 3k + 3

   = (k³ + 2k) + 3(k² + k + 1)

   = 3m + 3(k² + k + 1)     [by the inductive hypothesis]

   = 3(m + k² + k + 1).

   Since m + k² + k + 1 is an integer, 3 | ((k+1)³ + 2(k+1)). ✓

   Conclusion: By the principle of mathematical induction, 3 | (n³ + 2n) for all integers n ≥ 1.

10. Multi-part challenge. Problem Solving

    ▶ Show Answer

    (a) Prove 4 | (5ⁿ − 1) for all n ≥ 1:

    Base case n = 1: 5 − 1 = 4. 4 | 4. ✓

    Inductive hypothesis: Assume 4 | (5^k − 1), i.e. 5^k − 1 = 4m.

    5^k+1 − 1 = 5(5^k − 1) + 4 = 5(4m) + 4 = 4(5m + 1).

    Since 5m + 1 is an integer, 4 | (5^k+1 − 1). ✓

    By mathematical induction, 4 | (5ⁿ − 1) for all n ≥ 1.

    (b) 2ⁿ > n² fails at n = 4:

    At n = 4: 2⁴ = 16 and 4² = 16. So 2ⁿ = n² (not strictly greater). The strict inequality fails for n = 4.

    From Question 7, we proved 2ⁿ > n² for all n ≥ 5. So n = 5 is the smallest value for which the strict inequality holds.

    (c) Prove (5ⁿ − 1)/4 > n² for all n ≥ 5:

    This is equivalent to proving 5ⁿ − 1 > 4n².

    We prove this by induction. Base case n = 5: 5⁵ − 1 = 3125 − 1 = 3124 and 4(5²) = 100. Since 3124 > 100. ✓

    Inductive hypothesis: Assume 5^k − 1 > 4k² for some k ≥ 5.

    Inductive step:

    5^k+1 − 1 = 5 × 5^k − 1 = 5(5^k − 1) + 4 > 5 × 4k² + 4 = 20k² + 4. [by IH]

    We need 20k² + 4 ≥ 4(k+1)² = 4k² + 8k + 4, i.e. 16k² ≥ 8k, i.e. 2k ≥ 1.

    This holds for all k ≥ 1, and certainly for k ≥ 5. ✓

    Therefore 5^k+1 − 1 > 4(k+1)². By mathematical induction, (5ⁿ−1)/4 > n² for all n ≥ 5.