---
title: "Weak induction; 5^n − 1 divisible by 4"
subject: "Discrete Structure"
chapter: 1
key: "semester_4/discrete_structure:induction-5-power-n-minus-1-divisible-4"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/induction-5-power-n-minus-1-divisible-4
site: BCT Engineering
---

# Weak induction; 5^n − 1 divisible by 4

Discrete Structure · Chapter 1: Logic, Induction and Reasoning

- Asked in: 2073 Magh, 3+5 marks
- Video: [Discrete Math - 5.1.3 Proof Using Mathematical Induction - Divisibility](https://www.youtube.com/watch?v=OP3l8VUEE-8) — SawFin Mathematics
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/induction-5-power-n-minus-1-divisible-4
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-1

## Question

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.

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

## Answer

#### 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.
```text
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. ∎

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does the weak principle of induction require?
   A. P(n) for all n assumed
   B. Only the inductive step
   C. Basis P(n₀) and P(k) → P(k+1) for all k ≥ n₀
   D. Assuming all earlier cases P(n₀),…,P(k)
   Answer: C. Weak induction uses only the previous case P(k). (Key point: Weak induction)

2. The basis case n = 1 gives?
   A. 25 − 1 = 24
   B. 5 + 1 = 6
   C. 5 − 1 = 4, divisible by 4
   D. 1 − 1 = 0 only
   Answer: C. 5¹ − 1 = 4. (Key point: Basis)

3. How is 5ᵏ⁺¹ − 1 rewritten using the hypothesis?
   A. 5ᵏ − 1 + 4
   B. 4(5ᵏ) − 1
   C. 5(5ᵏ − 1) + 4 = 5(4m) + 4
   D. 5(5ᵏ + 1) − 4
   Answer: C. 5·5ᵏ − 1 = 5(5ᵏ − 1) + 4, which equals 4(5m + 1). (Key point: Key step)

## Related in Discrete Structure

- [Induction: 3+3·5+3·5²+...+3·5^n](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-sum-3-times-5-powers) — Discrete Structure, chapter 1, asked 2×
- [Induction: sum of geometric progression](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-geometric-series-sum) — Discrete Structure, chapter 1
- [Induction: sum of n(n+1)(n+2)](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-product-n-n1-n2) — Discrete Structure, chapter 1
- [Induction: n < 2^n](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-n-less-than-2-power-n) — Discrete Structure, chapter 1
- [Induction: sum of cubes](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-sum-of-cubes) — Discrete Structure, chapter 1, asked 2×
- [Induction: sum of squares](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-sum-of-squares) — Discrete Structure, chapter 1, asked 2×

## Related in other subjects

- [Induction: 5^n − 1 divisible by 4](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-five-power) — Theory of Computation, chapter 1, asked 2×
- [Induction: n⁴ − 4n² divisible by 3](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-n4-4n2) — Theory of Computation, chapter 1, asked 2×
- [Operating principle of 3-phase induction motor](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machines_i%3Ainduction-motor-operating-principle) — Electrical Machines I, chapter 5
- [Algorithm for numbers divisible by 9 not 6](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgo-flowchart-divisible-9-not-6) — Computer Programming, chapter 2