---
title: "Induction: sum of squares"
subject: "Discrete Structure"
chapter: 1
key: "semester_4/discrete_structure:induction-sum-of-squares"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/induction-sum-of-squares
site: BCT Engineering
---

# Induction: sum of squares

Discrete Structure · Chapter 1: Logic, Induction and Reasoning

- Asked in: 2070 Magh, 8 marks
- Video: [Mathematical Induction Proof for the Sum of Squares](https://www.youtube.com/watch?v=JiBd5yyYfUE) — The Math Sorcerer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/induction-sum-of-squares
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-1

## Question

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

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

## Answer

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

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

## Check yourself

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

1. At n = 1, n(n+1)(2n+1)/6 equals?
   A. 2
   B. 3
   C. 6
   D. 1
   Answer: D. 1·2·3/6 = 1. (Key point: Basis)

2. Which term is added in the inductive step?
   A. k²
   B. (k+2)²
   C. 2k+1
   D. (k+1)²
   Answer: D. The (k+1)th square. (Key point: Added term)

3. After factoring (k+1)/6, the bracket is?
   A. k(2k+1) + (k+1)
   B. 2k+1+6
   C. k + 6(k+1)
   D. k(2k+1) + 6(k+1)
   Answer: D. (k+1)² = (k+1)·6(k+1)/6. (Key point: Combine)

4. 2k² + 7k + 6 factors as?
   A. (k+3)(2k+2)
   B. (2k+1)(k+6)
   C. (k+1)(2k+6)
   D. (k+2)(2k+3)
   Answer: D. (k+2)(2k+3) = 2k² + 7k + 6. (Key point: Factorisation)

## Close variants set in other exams

- [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×

## Related in Discrete Structure

- [Induction: alternating sum of squares](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-alternating-squares) — Discrete Structure, chapter 1
- [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: 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: 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

## Related in other subjects

- [Induction: sum of k·k! = (n+1)!−1](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-factorial-sum) — Theory of Computation, chapter 1, asked 2×
- [Sum and average between M and N using pointer](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Apointer-sum-average-range) — Computer Programming, chapter 9
- [Sum of digits processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-sum-of-digits) — Embedded System, chapter 2
- [Equal positive and negative sequence impedances](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Astatic-circuit-positive-negative-equal) — Power System Analysis II, chapter 4