Skip to main content

Induction: sum of squares

Short answer

Basis n=1: 1²=1·2·3/6. Assume sum to k = k(k+1)(2k+1)/6. Adding (k+1)² and factoring gives (k+1)(2k²+7k+6)/6 = (k+1)(k+2)(2k+3)/6. Proved by induction.

Use mathematical induction to show that 1² + 2² + ... + n² = n(n+1)(2n+1)/6 whenever n is a positive integer.

To prove. P(n): 1² + 2² + … + n² = n(n+1)(2n+1)/6 for all positive integers n.

Basis step (n = 1)

  • LHS = 1² = 1.
  • RHS = 1·2·3/6 = 1.
  • P(1) is true.

Inductive hypothesis

Assume P(k): 1² + 2² + … + k² = k(k+1)(2k+1)/6.

Inductive step

Show P(k+1): 1² + … + k² + (k+1)² = (k+1)(k+2)(2k+3)/6.

LHS = k(k+1)(2k+1)/6 + (k+1)²              (hypothesis)
    = (k+1) [ k(2k+1) + 6(k+1) ] / 6
    = (k+1) (2k² + k + 6k + 6) / 6
    = (k+1) (2k² + 7k + 6) / 6
    = (k+1) (k+2) (2k+3) / 6   = RHS

(Check: (k+2)(2k+3) = 2k² + 3k + 4k + 6 = 2k² + 7k + 6.)

Conclusion

By mathematical induction, the formula holds for all positive integers n. ∎

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 1 questions →