Solutions — Proof by Induction: Divisibility

Step 1 — Base case (n = 1):

2¹ − 1 = 1, which is odd. ✓

Step 2 — Inductive hypothesis:

Assume 2^k − 1 is odd for some integer k ≥ 1.

That is, 2^k − 1 = 2m − 1 for some integer m, so 2^k = 2m.

Step 3 — Inductive step: Show 2^k+1 − 1 is odd.

2^k+1 − 1 = 2 · 2^k − 1

= 2(2m) − 1     [substituting 2^k = 2m from the hypothesis]

= 4m − 1 = 2(2m) − 1

This is of the form (even) − 1 = odd. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 2ⁿ − 1 is odd for all integers n ≥ 1.

Step 1 — Base case (n = 1):

1³ − 1 = 0 = 3(0). ✓

Step 2 — Inductive hypothesis:

Assume k³ − k = 3m for some integer m.

Step 3 — Inductive step: Show (k+1)³ − (k+1) is divisible by 3.

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

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

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

= 3(m + k² + k)

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

Step 4 — Conclusion:

By the principle of mathematical induction, n³ − n is divisible by 3 for all integers n ≥ 1.

Step 1 — Base case (n = 1):

4¹ − 1 = 3 = 3(1). ✓

Step 2 — Inductive hypothesis:

Assume 4^k − 1 = 3m for some integer m, so 4^k = 3m + 1.

Step 3 — Inductive step: Show 4^k+1 − 1 is divisible by 3.

4^k+1 − 1 = 4 · 4^k − 1

= 4(3m + 1) − 1     [substituting 4^k = 3m + 1]

= 12m + 4 − 1 = 12m + 3 = 3(4m + 1)

Since 4m + 1 is an integer, 4^k+1 − 1 is divisible by 3. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 4ⁿ − 1 is divisible by 3 for all integers n ≥ 1.

Step 1 — Base case (n = 1):

7¹ − 1 = 6 = 6(1). ✓

Step 2 — Inductive hypothesis:

Assume 7^k − 1 = 6m for some integer m, so 7^k = 6m + 1.

Step 3 — Inductive step: Show 7^k+1 − 1 is divisible by 6.

7^k+1 − 1 = 7 · 7^k − 1

= 7(6m + 1) − 1     [substituting 7^k = 6m + 1]

= 42m + 7 − 1 = 42m + 6 = 6(7m + 1)

Since 7m + 1 is an integer, 7^k+1 − 1 is divisible by 6. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 7ⁿ − 1 is divisible by 6 for all integers n ≥ 1.

Step 1 — Base case (n = 1):

3¹ − 1 = 2 = 2(1). ✓

Step 2 — Inductive hypothesis:

Assume 3^k − 1 = 2m for some integer m, so 3^k = 2m + 1.

Step 3 — Inductive step: Show 3^k+1 − 1 is divisible by 2.

3^k+1 − 1 = 3 · 3^k − 1

= 3(2m + 1) − 1     [substituting 3^k = 2m + 1]

= 6m + 3 − 1 = 6m + 2 = 2(3m + 1)

Since 3m + 1 is an integer, 3^k+1 − 1 is divisible by 2. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 3ⁿ − 1 is divisible by 2 for all integers n ≥ 1.

Step 1 — Base case (n = 1):

5¹ − 1 = 4 = 4(1). ✓

Step 2 — Inductive hypothesis:

Assume 5^k − 1 = 4m for some integer m, so 5^k = 4m + 1.

Step 3 — Inductive step: Show 5^k+1 − 1 is divisible by 4.

5^k+1 − 1 = 5 · 5^k − 1

= 5(4m + 1) − 1     [substituting 5^k = 4m + 1]

= 20m + 5 − 1 = 20m + 4 = 4(5m + 1)

Since 5m + 1 is an integer, 5^k+1 − 1 is divisible by 4. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 5ⁿ − 1 is divisible by 4 for all integers n ≥ 1.

Step 1 — Base case (n = 1):

1 × 2 × 3 = 6 = 6(1). ✓

Step 2 — Inductive hypothesis:

Assume k(k+1)(k+2) = 6m for some integer m.

Step 3 — Inductive step: Show (k+1)(k+2)(k+3) is divisible by 6.

(k+1)(k+2)(k+3)

= (k+1)(k+2) · (k+3)

Note that (k+1)(k+2)(k+3) − k(k+1)(k+2) = (k+1)(k+2)[(k+3) − k] = 3(k+1)(k+2)

So (k+1)(k+2)(k+3) = k(k+1)(k+2) + 3(k+1)(k+2) = 6m + 3(k+1)(k+2)

Now, among the consecutive integers (k+1) and (k+2), one must be even, so (k+1)(k+2) = 2t for some integer t.

Therefore (k+1)(k+2)(k+3) = 6m + 3(2t) = 6m + 6t = 6(m + t).

Since m + t is an integer, (k+1)(k+2)(k+3) is divisible by 6. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, n(n+1)(n+2) is divisible by 6 for all integers n ≥ 1.

Observation: 2²ⁿ = (2²)ⁿ = 4ⁿ, so we are proving 4ⁿ − 1 is divisible by 3.

Step 1 — Base case (n = 1):

2²⁽¹⁾ − 1 = 4 − 1 = 3 = 3(1). ✓

Step 2 — Inductive hypothesis:

Assume 2^2k − 1 = 3m for some integer m, so 2^2k = 3m + 1.

Step 3 — Inductive step: Show 2^2(k+1) − 1 is divisible by 3.

2^2(k+1) − 1 = 2^2k+2 − 1 = 4 · 2^2k − 1

= 4(3m + 1) − 1     [substituting 2^2k = 3m + 1]

= 12m + 4 − 1 = 12m + 3 = 3(4m + 1)

Since 4m + 1 is an integer, 2^2(k+1) − 1 is divisible by 3. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 2²ⁿ − 1 is divisible by 3 for all integers n ≥ 1.

Part (a):

Step 1 — Base case (n = 1):

6¹ − 1 = 5 = 5(1). ✓

Step 2 — Inductive hypothesis:

Assume 6^k − 1 = 5m for some integer m, so 6^k = 5m + 1.

Step 3 — Inductive step: Show 6^k+1 − 1 is divisible by 5.

6^k+1 − 1 = 6 · 6^k − 1

= 6(5m + 1) − 1 = 30m + 6 − 1 = 30m + 5 = 5(6m + 1)

Since 6m + 1 is an integer, 6^k+1 − 1 is divisible by 5. ✓

Step 4 — Conclusion:

By the principle of mathematical induction, 6ⁿ − 1 is divisible by 5 for all integers n ≥ 1.

Part (b):

From part (a), 6ⁿ − 1 = 5m for some integer m, so:

6ⁿ + 4 = (6ⁿ − 1) + 5 = 5m + 5 = 5(m + 1)

Since m + 1 is an integer, 6ⁿ + 4 is divisible by 5. ✓

Part (a) — Proof by Induction:

Step 1 — Base case (n = 1):

1³ + 2(1) = 1 + 2 = 3 = 3(1). ✓

Step 2 — Inductive hypothesis:

Assume k³ + 2k = 3m for some integer m.

Step 3 — Inductive step: Show (k+1)³ + 2(k+1) is divisible by 3.

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

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

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

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

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

Step 4 — Conclusion:

By the principle of mathematical induction, n³ + 2n is divisible by 3 for all integers n ≥ 1.

Part (b) — Direct Algebraic Argument:

n³ + 2n = n(n² + 2) = n(n² − 1 + 3) = n(n − 1)(n + 1) + 3n

= (n − 1) · n · (n + 1) + 3n

The product of three consecutive integers (n − 1), n, (n + 1) is always divisible by 6 (and hence by 3).

Also, 3n is divisible by 3.

Therefore their sum n³ + 2n = (n − 1)n(n + 1) + 3n is divisible by 3. ✓