Sum of Sequence of Squares
Theorem
- $\ds \forall n \in \N: \sum_{i \mathop = 1}^n i^2 = \frac {n \paren {n + 1} \paren {2 n + 1} } 6$
Proof by Induction
Proof by induction:
For all $n \in \N$, let $\map P n$ be the proposition:
- $\ds \sum_{i \mathop = 1}^n i^2 = \frac {n \paren {n + 1} \paren {2 n + 1} } 6$
When $n = 0$, we see from the definition of vacuous sum that:
- $0 = \ds \sum_{i \mathop = 1}^0 i^2 = \frac {0 \paren 1 \paren 1} 6 = 0$
and so $\map P 0$ holds.
Basis for the Induction
When $n = 1$:
- $\ds \sum_{i \mathop = 1}^1 i^2 = 1^2 = 1$
Now, we have:
- $\ds \frac {n \paren {n + 1} \paren {2 n + 1} } 6 = \frac {1 \paren {1 + 1} \paren {2 \times 1 + 1} } 6 = \frac 6 6 = 1$
and $\map P 1$ is seen to hold.
This is our basis for the induction.
Induction Hypothesis
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
- $\ds \sum_{i \mathop = 1}^k i^2 = \frac {k \paren {k + 1} \paren {2 k + 1} } 6$
Then we need to show:
- $\ds \sum_{i \mathop = 1}^{k + 1} i^2 = \frac {\paren {k + 1} \paren {k + 2} \paren {2 \paren {k + 1} + 1} } 6$
Induction Step
This is our induction step:
Using the properties of summation, we have:
- $\ds \sum_{i \mathop = 1}^{k + 1} i^2 = \sum_{i \mathop = 1}^k i^2 + \paren {k + 1}^2$
We can now apply our induction hypothesis, obtaining:
\(\ds \sum_{i \mathop = 1}^{k + 1} i^2\) | \(=\) | \(\ds \frac {k \paren {k + 1} \paren {2 k + 1} } 6 + \paren {k + 1}^2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {k \paren {k + 1} \paren {2 k + 1} + 6 \paren {k + 1}^2} 6\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {k + 1} \paren {k \paren {2 k + 1} + 6 \paren {k + 1} } } 6\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {k + 1} \paren {2 k^2 + 7 k + 6} } 6\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {k + 1} \paren {k + 2} \paren {2 \paren {k + 1} + 1} } 6\) |
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\ds \forall n \in \N: \sum_{i \mathop = 1}^n i^2 = \frac {n \paren {n + 1} \paren {2 n + 1} } 6$
$\blacksquare$
Proof by Products of Consecutive Integers
\(\ds \sum_{i \mathop = 1}^n 3 i \paren {i + 1}\) | \(=\) | \(\ds n \paren {n + 1} \paren {n + 2}\) | Sum of Sequence of Products of Consecutive Integers | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{i \mathop = 1}^n 3 i^2 + \sum_{i \mathop = 1}^n 3 i\) | \(=\) | \(\ds n \paren {n + 1} \paren {n + 2}\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{i \mathop = 1}^n 3 i^2\) | \(=\) | \(\ds n \paren {n + 1} \paren {n + 2} - 3 \frac {n \paren {n + 1} } 2\) | Closed Form for Triangular Numbers | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds \frac {n \paren {n + 1} \paren {n + 2} } 3 - \frac {n \paren {n + 1} } 2\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds \frac {2 n \paren {n + 1} \paren {n + 2} - 3 n \paren {n + 1} } 6\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds \frac {n \paren {n + 1} \paren {2 n + 1} } 6\) |
$\blacksquare$
Proof by Telescoping Series
Observe that:
- $3 i \paren {i + 1} = i \paren {i + 1} \paren {i + 2} - i \paren {i + 1} \paren {i - 1}$
That is:
- $(1): \quad 6 T_i = \paren {i + 1} \paren {\paren {i + 1} + 1} \paren {\paren {i + 1} - 1} - i \paren {i + 1} \paren {i - 1}$
Then:
\(\ds n^2\) | \(=\) | \(\ds \frac {n^2 + n + n^2 - n} 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n \paren {n + 1} + n \paren {n - 1} } 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n \paren {n + 1} } 2 + \frac {n \paren {n - 1} } 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds T_n + T_{n-1}\) |
where $T_n$ is the $n$th Triangular number.
Then:
\(\ds \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds 1 + \paren {T_1 + T_2} + \paren {T_2 + T_3} + \paren {T_3 + T_4} + \cdots + \paren {T_{n - 1} + T_n}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 + 2 T_2 + 2 T_3 + 2 T_4 + \cdots + 2 T_{n - 1} + T_n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 - T_1 - T_n + 2 \paren {T_1 + T_2 + T_3 + T_4 + \cdots + T_n}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 2 \paren {\sum_{i \mathop = 1}^n T_i} - \frac {n \paren {n + 1} } 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 2 \paren {\frac {n \paren {n + 1} \paren {n + 2} } 6} - \frac {n \paren {n + 1} } 2\) | Telescoping Series from $(1)$ above | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {2 n \paren {n^2 + 3 n + 2} - \paren {3 n^2 + 3 n} } 6\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {2 n^3 + 3 n^2 + n} 6\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n \paren {n + 1} \paren {2 n + 1} } 6\) |
$\blacksquare$
Proof by Summation of Summations
We can observe from the above diagram that:
- $\ds \forall n \in \N: \sum_{i \mathop = 1}^n i^2 = \sum_{i \mathop = 1}^n \paren {\sum_{j \mathop = i}^n j}$
Therefore we have:
\(\ds \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \paren {\sum_{j \mathop = i}^n j}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \paren {\sum_{j \mathop = 1}^n j - \sum_{j \mathop = 1}^{i - 1} j}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \paren {\frac {n \paren {n + 1} } 2 - \frac {i \paren {i - 1} } 2}\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds 2 \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds n^2 \paren {n + 1} - \sum_{i \mathop = 1}^n i^2 + \sum_{i \mathop = 1}^n i\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds 3 \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds n^2 \paren {n + 1} + \sum_{i \mathop = 1}^n i\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds 3 \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds n^2 \paren {n + 1} + \frac {n \paren {n + 1} } 2\) | Closed Form for Triangular Numbers | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds 6 \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds 2 n^2 \paren {n + 1} + n \paren {n + 1}\) | |||||||||||
\(\ds \) | \(=\) | \(\ds n \paren {n + 1} \paren {2 n + 1}\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds \frac {n \paren {n + 1} \paren {2 n + 1} } 6\) |
$\blacksquare$
Proof by Sum of Differences of Cubes
\(\ds \sum_{i \mathop = 1}^n \paren {\paren {i + 1}^3 - i^3}\) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \paren {i^3 + 3 i^2 + 3 i + 1 - i^3}\) | Binomial Theorem | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \paren {3 i^2 + 3 i + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 3 \sum_{i \mathop = 1}^n i^2 + 3 \sum_{i \mathop = 1}^n i + \sum_{i \mathop = 1}^n 1\) | Summation is Linear | |||||||||||
\(\ds \) | \(=\) | \(\ds 3\sum_{i \mathop = 1}^n i^2 + 3 \frac {n \paren {n + 1} } 2 + n\) | Closed Form for Triangular Numbers |
On the other hand:
\(\ds \sum_{i \mathop = 1}^n \paren {\paren {i + 1}^3 - i^3}\) | \(=\) | \(\ds \paren {n + 1}^3 - n^3 + n^3 - \paren {n - 1}^3 + \paren {n - 1}^3 - \cdots + 2^3 - 1^3\) | Definition of Summation | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {n + 1}^3 - 1^3\) | Telescoping Series: Example 2 | |||||||||||
\(\ds \) | \(=\) | \(\ds n^3 + 3n^2 + 3n + 1 - 1\) | Binomial Theorem | |||||||||||
\(\ds \) | \(=\) | \(\ds n^3 + 3n^2 + 3n\) |
Therefore:
\(\ds 3 \sum_{i \mathop = 1}^n i^2 + 3 \frac {n \paren {n + 1} } 2 + n\) | \(=\) | \(\ds n^3 + 3 n^2 + 3 n\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds 3 \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds n^3 + 3 n^2 + 3 n - 3 \frac {n \paren {n + 1} } 2 - n\) |
Therefore:
\(\ds \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds \frac 1 3 \paren {n^3 + 3 n^2 + 3 n - 3 \frac {n \paren {n + 1} }2 - n}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 3 \paren {n^3 + 3 n^2 + 3 n - \frac {3 n^2} 2 - \frac {3 n} 2 - n}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 3 \paren {n^3 + \frac {3 n^2} 2 + \frac n 2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 6 n \paren {2 n^2 + 3 n + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 6 n \paren {n + 1} \paren {2 n + 1}\) |
$\blacksquare$
Proof by Binomial Coefficients
From Binomial Coefficient with One:
- $\dbinom n 1 = n$
From Binomial Coefficient with Two:
- $\dbinom n 2 = \dfrac {n \paren {n - 1} } 2$
Thus:
\(\ds 2 \binom n 2 + \binom n 1\) | \(=\) | \(\ds 2 \dfrac {n \paren {n - 1} } 2 + n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds n \paren {n - 1} + n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds n^2\) |
Hence:
\(\ds \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds \sum_{i \mathop = 1}^n \paren {2 \binom i 2 + \binom i 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 2 \binom {n + 1} 3 + \binom {n + 1} 2\) | Sum of Binomial Coefficients over Upper Index | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {2 \paren {n + 1} n \paren {n - 1} } {3 \times 2 \times 1} + \frac {\paren {n + 1} n} 2\) | Definition of Binomial Coefficient | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n \paren {n + 1} \paren {2 n + 1} } 6\) | after algebra |
$\blacksquare$
Proof using Bernoulli Numbers
From Faulhaber's Formula:
\(\ds \sum_{i \mathop = 1}^n i^p\) | \(=\) | \(\ds 1^p + 2^p + \cdots + n^p\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n^{p + 1} } {p + 1} + \sum_{k \mathop = 1}^p \frac {B_k \, p^{\underline {k - 1} } \, n^{p - k + 1} } {k!}\) |
where $B_k$ are the Bernoulli numbers.
Setting $p = 2$:
\(\ds \sum_{i \mathop = 1}^n i^2\) | \(=\) | \(\ds 1^2 + 2^2 + \cdots + n^2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n^{2 + 1} } {2 + 1} + \frac {B_1 \, p^{\underline 0} \, n^2} {1!} + \frac {B_2 \, p^{\underline 1} \, n^1} {2!}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n^3} 3 + B_1 n^2 + B_2 n\) | Definition of Falling Factorial and simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n^3} 3 + \frac {n^2} 2 + \frac n 6\) | Definition of Bernoulli Numbers | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {n \paren {n + 1} \paren {2 n + 1} } 6\) | after algebra |
Hence the result.
$\blacksquare$
Also presented as
The Sum of Sequence of Squares can also be presented as:
- $\ds \forall n \in \N: \sum_{i \mathop = 0}^n i^2 = \frac {n \paren {n + 1} \paren {2 n + 1} } 6$
This is seen to be equivalent to the given form by the fact that the first term evaluates to $\dfrac {0 \paren {0 + 1} \paren {2 \times 0 + 1} } 6$ which is zero.
Also see
Historical Note
The closed-form expression for the Sum of Sequence of Squares was proved by Archimedes during the course of his proofs of the volumes of various solids of revolution in his On Conoids and Spheroids.
It was also documented by Aryabhata the Elder in his work Aryabhatiya of $499$ CE.
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 18$: Induced $N$-ary Operations: Exercise $18.10 \ \text{(b)}$
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {1-1}$ Principle of Mathematical Induction: Exercise $1$
- 1971: Robert H. Kasriel: Undergraduate Topology ... (previous) ... (next): $\S 1.17$: Finite Induction and Well-Ordering for Positive Integers: Exercise $3$
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Appendix $\text{A}.6$: Mathematical Induction: Problem Set $\text{A}.6$: $36$
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: $1.3$ Inductive Proofs
- 1992: George F. Simmons: Calculus Gems ... (previous) ... (next): Chapter $\text {A}.5$: Archimedes (ca. $\text {287}$ – $\text {212}$ B.C.)