Skip to main content

Induction: n⁴ − 4n² divisible by 3

Short answer

Base n=0 holds. For n=k+1, (k+1)⁴–4(k+1)² = (k⁴–4k²) + 4(k³–k) + 3(2k²–1). Each term is divisible by 3: first by hypothesis; second because k³–k is a product of three consecutive integers; third is a multiple of 3.

Use the principle of mathematical induction to prove that n⁴ − 4n² is divisible by 3 for n ≥ 0.

Let P(n): n⁴ − 4n² is divisible by 3. We prove P(n) for all n ≥ 0.

Basis (n = 0)

0⁴ − 4·0² = 0 = 3·0, so P(0) is true.

Induction hypothesis

Assume P(k): k⁴ − 4k² = 3m for some integer m.

Induction step

Expand (k+1)⁴ − 4(k+1)²:

(k+1)⁴ − 4(k+1)² = (k⁴ + 4k³ + 6k² + 4k + 1) − 4(k² + 2k + 1)
                 = k⁴ − 4k² + 4k³ + 6k² − 4k − 3
                 = (k⁴ − 4k²) + 4(k³ − k) + 3(2k² − 1)
  • (k⁴ − 4k²) = 3m by the hypothesis.
  • 3(2k² − 1) is a multiple of 3.
  • 4(k³ − k): we show k³ − k is divisible by 3 (small lemma Q(k)).
    • Q(0): 0 − 0 = 0 is divisible by 3.
    • If k³ − k = 3t, then (k+1)³ − (k+1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3(k² + k) = 3(t + k² + k), divisible by 3.

Hence all three terms are multiples of 3, so (k+1)⁴ − 4(k+1)² is divisible by 3, i.e. P(k+1) holds.

Conclusion

By induction, n⁴ − 4n² is divisible by 3 for all n ≥ 0. ∎

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 1 questions →