Sum of Sequence of Squares

From ProofWiki
Jump to: navigation, search

Theorem

$\displaystyle \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:

$\displaystyle \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 = \displaystyle \sum_{i \mathop = 1}^0 i^2 = \frac {0 \paren 1 \paren 1} 6 = 0$

and so $P(0)$ holds.


Basis for the Induction

When $n = 1$:

$\displaystyle \sum_{i \mathop = 1}^1 i^2 = 1^2 = 1$

Now, we have:

$\displaystyle \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 $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:

$\displaystyle \sum_{i \mathop = 1}^k i^2 = \frac {k \paren {k + 1} \paren {2 k + 1} } 6$


Then we need to show:

$\displaystyle \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:

$\displaystyle \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:

\(\displaystyle \sum_{i \mathop = 1}^{k + 1} i^2\) \(=\) \(\displaystyle \frac {k \paren {k + 1} \paren {2 k + 1} } 6 + \paren {k + 1}^2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {k \paren {k + 1} \paren {2 k + 1} + 6 \paren {k + 1}^2} 6\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {\paren {k + 1} \paren {k \paren {2 k + 1} + 6 \paren {k + 1} } } 6\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {\paren {k + 1} \paren {2 k^2 + 7 k + 6} } 6\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {\paren {k + 1} \paren {k + 2} \paren {2 \paren {k + 1} + 1} } 6\) $\quad$ $\quad$

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\displaystyle \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

\(\displaystyle \sum_{i \mathop = 1}^n 3 i \left({i + 1}\right)\) \(=\) \(\displaystyle n \left({n + 1}\right) \left({n + 2}\right)\) $\quad$ Sum of Sequence of Products of Consecutive Integers $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \sum_{i \mathop = 1}^n 3 i^2 + \sum_{i \mathop = 1}^n 3 i\) \(=\) \(\displaystyle n \left({n + 1}\right) \left({n + 2}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \sum_{i \mathop = 1}^n 3 i^2\) \(=\) \(\displaystyle n \left({n + 1}\right) \left({n + 2}\right) - 3 \frac {n \left({n + 1}\right) } 2\) $\quad$ Closed Form for Triangular Numbers $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \frac {n \left({n + 1}\right) \left({n + 2}\right)} 3 - \frac {n \left({n + 1}\right) } 2\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \frac {2 n \left({n + 1}\right) \left({n + 2}\right) - 3 n \left({n + 1}\right) } 6\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \frac {n \left({n + 1}\right) \left({2 n + 1}\right)} 6\) $\quad$ $\quad$

$\blacksquare$


Proof by Telescoping Series

Observe that:

$3 i \left({i + 1}\right) = i \left({i + 1}\right) \left({i + 2}\right) - i \left({i + 1}\right) \left({i - 1}\right)$

That is:

$(1): \quad 6 T_i = \left({i + 1}\right) \left({\left({i + 1}\right) + 1}\right) \left({\left({i + 1}\right) - 1}\right) - i \left({i + 1}\right) \left({i - 1}\right)$


Then:

\(\displaystyle n^2\) \(=\) \(\displaystyle \frac {n^2 + n + n^2 - n} 2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n \left({n + 1}\right) + n \left({n - 1}\right)} 2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n \left({n + 1}\right)} 2 + \frac {n \left({n - 1}\right)} 2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle T_n + T_{n-1}\) $\quad$ $\quad$

where $T_n$ is the $n$th Triangular number.


Then:

\(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle 1 + \left({T_1 + T_2}\right) + \left({T_2 + T_3}\right) + \left({T_3 + T_4}\right) + \cdots + \left({T_{n - 1} + T_n}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 1 + 2 T_2 + 2 T_3 + 2 T_4 + \cdots + 2 T_{n - 1} + T_n\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 1 - T_1 - T_n + 2 \left({T_1 + T_2 + T_3 + T_4 + \cdots + T_n}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 2 \left({\sum_{i \mathop = 1}^n T_i} \right) - \frac {n \left({n + 1}\right)} 2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 2 \left({\frac {n \left({n + 1}\right) \left({n + 2}\right)} 6}\right) - \frac {n \left({n + 1}\right)} 2\) $\quad$ Telescoping Series from $(1)$ above $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {2 n \left({n^2 + 3 n + 2}\right) - \left({3 n^2 + 3 n}\right)} 6\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {2 n^3 + 3 n^2 + n} 6\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n \left({n + 1}\right) \left({2 n + 1}\right)} 6\) $\quad$ $\quad$

$\blacksquare$


Proof by Summation of Summations

Sum of Sequences of Squares.jpg

We can observe from the above diagram that:

$\displaystyle \forall n \in \N: \sum_{i \mathop = 1}^n i^2 = \sum_{i \mathop = 1}^n \left({\sum_{j \mathop = i}^n j}\right)$

Therefore we have:

\(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left({\sum_{j \mathop = i}^n j}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left( {\sum_{j \mathop = 1}^n j - \sum_{j \mathop = 1}^{i - 1} j} \right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left({\frac {n \left({n + 1}\right)} 2 - \frac {i \left({i - 1}\right)} 2}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle 2 \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle n^2 \left({n + 1}\right) - \sum_{i \mathop = 1}^n i^2 + \sum_{i \mathop = 1}^n i\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle 3 \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle n^2 \left({n + 1}\right) + \sum_{i \mathop = 1}^n i\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle 3 \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle n^2 \left({n + 1}\right) + \frac {n \left({n + 1}\right)} 2\) $\quad$ Closed Form for Triangular Numbers $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle 6 \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle 2 n^2 \left({n + 1}\right) + n \left({n + 1}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n \left({n + 1}\right) \left({2 n + 1}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \frac {n \left({n + 1}\right) \left({2 n + 1}\right)} 6\) $\quad$ $\quad$

$\blacksquare$


Proof by Sum of Differences of Cubes

\(\displaystyle \sum_{i \mathop = 1}^n \left({\left({i + 1}\right)^3 - i^3}\right)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left({i^3 + 3 i^2 + 3 i + 1 - i^3}\right)\) $\quad$ Binomial Theorem $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left({3 i^2 + 3 i + 1}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 3 \sum_{i \mathop = 1}^n i^2 + 3 \sum_{i \mathop = 1}^n i + \sum_{i \mathop = 1}^n 1\) $\quad$ Summation is Linear $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 3\sum_{i \mathop = 1}^n i^2 + 3 \frac {n \left({n + 1}\right)} 2 + n\) $\quad$ Closed Form for Triangular Numbers $\quad$

On the other hand:

\(\displaystyle \sum_{i \mathop = 1}^n \left({\left({i + 1}\right)^3 - i^3}\right)\) \(=\) \(\displaystyle \left({n + 1}\right)^3 - n^3 + n^3 - \left({n - 1}\right)^3 + \left({n - 1}\right)^3 - \cdots + 2^3 - 1^3\) $\quad$ Definition of Summation $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({n + 1}\right)^3 - 1^3\) $\quad$ Telescoping Series: Example 2 $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n^3 + 3n^2 + 3n + 1 - 1\) $\quad$ Binomial Theorem $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n^3 + 3n^2 + 3n\) $\quad$ $\quad$

Therefore:

\(\displaystyle 3 \sum_{i \mathop = 1}^n i^2 + 3 \frac {n \left({n + 1}\right)} 2 + n\) \(=\) \(\displaystyle n^3 + 3 n^2 + 3 n\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle 3 \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle n^3 + 3 n^2 + 3 n - 3 \frac {n \left({n + 1}\right)} 2 - n\) $\quad$ $\quad$

Therefore:

\(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \frac 1 3 \left({n^3 + 3 n^2 + 3 n - 3 \frac {n \left({n + 1}\right)}2 - n}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 3 \left({n^3 + 3 n^2 + 3 n - \frac {3 n^2} 2 - \frac {3 n} 2 - n}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 3 \left({n^3 + \frac {3 n^2} 2 + \frac n 2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 6 n \left({2 n^2 + 3 n + 1}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 6 n \left({n + 1}\right) \left({2 n + 1}\right)\) $\quad$ $\quad$

$\blacksquare$


Proof by Binomial Coefficients

From Binomial Coefficient with One:

$\dbinom n 1 = n$

From Binomial Coefficient with Two:

$\dbinom n 2 = \dfrac {n \left({n - 1}\right)} 2$


Thus:

\(\displaystyle 2 \binom n 2 + \binom n 1\) \(=\) \(\displaystyle 2 \dfrac {n \left({n - 1}\right)} 2 + n\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n \left({n - 1}\right) + n\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n^2\) $\quad$ $\quad$

Hence:

\(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \left({2 \binom i 2 + \binom i 1}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 2 \binom {n + 1} 3 + \binom {n + 1} 2\) $\quad$ Sum of Binomial Coefficients over Upper Index $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {2 \left({n + 1}\right) n \left({n - 1}\right)} {3 \times 2 \times 1} + \frac {\left({n + 1}\right) n} 2\) $\quad$ Definition of Binomial Coefficient $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n \left({n + 1}\right) \left({2 n + 1}\right)} 6\) $\quad$ after algebra $\quad$

$\blacksquare$


Proof using Bernoulli Numbers

From Sum of Powers of Positive Integers:

\(\displaystyle \sum_{i \mathop = 1}^n i^p\) \(=\) \(\displaystyle 1^p + 2^p + \cdots + n^p\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^{p + 1} } {p + 1} + \sum_{k \mathop = 1}^p \frac {B_k \, p^{\underline {k - 1} } \, n^{p - k + 1} } {k!}\) $\quad$ $\quad$

where $B_k$ are the Bernoulli numbers.


Setting $p = 2$:

\(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle 1^2 + 2^2 + \cdots + n^2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^{2 + 1} } {2 + 1} + \frac {B_1 \, p^{\underline 0} \, n^2} {1!} + \frac {B_2 \, p^{\underline 1} \, n^1} {2!}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^3} 3 + B_1 n^2 + B_2 n\) $\quad$ Definition of Falling Factorial and simplification $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n^3} 3 + \frac {n^2} 2 + \frac n 6\) $\quad$ Definition of Bernoulli Numbers $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n \left({n + 1}\right) \left({2 n + 1}\right)} 6\) $\quad$ after algebra $\quad$

Hence the result.

$\blacksquare$


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 Āryabhaṭīya of $499$ CE.


Sources