Skip to main content

Weak induction; 5^n − 1 divisible by 4

Short answer

Weak induction proves P(n₀) and P(k) ⇒ P(k+1). Basis n=1: 5¹−1=4 divisible by 4. Assume 5ᵏ−1=4m. Then 5^(k+1)−1 = 5·5ᵏ−1 = 5(4m+1)−1 = 4(5m+1), so divisible by 4 for all n≥1.

What do you mean by weak principle of mathematical induction? Prove that 5^n − 1 is divisible by 4 for all n ≥ 1 using Induction method.

Weak principle of mathematical induction

To prove that a statement P(n) is true for all integers n ≥ n₀:

  1. Basis step: show P(n₀) is true.
  2. Inductive step: show that for every k ≥ n₀, if P(k) is true then P(k+1) is true.

Then P(n) is true for all n ≥ n₀. It is "weak" because the inductive step uses only the single previous case P(k). (Strong induction assumes all of P(n₀), …, P(k).) In symbols: [P(n₀) ∧ ∀k (P(k) → P(k+1))] → ∀n P(n).

Proof that 5ⁿ − 1 is divisible by 4 for n ≥ 1

P(n): 4 divides 5ⁿ − 1.

Basis (n = 1). 5¹ − 1 = 4 = 4 × 1, divisible by 4. P(1) is true.

Inductive hypothesis. Assume P(k): 5ᵏ − 1 = 4m for some integer m.

Inductive step. Consider 5ᵏ⁺¹ − 1.

5ᵏ⁺¹ − 1 = 5·5ᵏ − 1
          = 5(5ᵏ − 1) + 5 − 1
          = 5(4m) + 4            (hypothesis)
          = 4(5m + 1)

5m + 1 is an integer, so 5ᵏ⁺¹ − 1 is divisible by 4. P(k+1) is true.

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 1 questions →