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 \left({n + 1}\right) \left({2 n + 1}\right)} 6$


Proof 1

Proof by induction:

For all $n \in \N$, let $P \left({n}\right)$ be the proposition:

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


When $n = 0$, we see from the definition of vacuous sum that:

$0 = \displaystyle \sum_{i \mathop = 1}^0 i^2 = \frac{0 \left({1}\right)\left({1}\right)} 6 = 0$

and so $P(0)$ holds.


Base Case

When $n=1$, we have $\displaystyle \sum_{i \mathop = 1}^1 i^2 = 1^2 = 1$.

Now, we have:

$\displaystyle \frac {n \left({n + 1}\right) \left({2 n + 1}\right)} 6 = \frac {1 \left({1 + 1}\right) \left({2 \cdot 1 + 1}\right)} 6 = \frac 6 6 = 1$

So $P(1)$ is true. This is our base case.


Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 1$, then it logically follows that $P \left({k+1}\right)$ is true.


So this is our induction hypothesis:

$\displaystyle \sum_{i \mathop = 1}^k i^2 = \frac {k \left({k + 1}\right) \left({2 k + 1}\right)} 6$


Then we need to show:

$\displaystyle \sum_{i \mathop = 1}^{k+1} i^2 = \frac{\left({k+1}\right) \left({k+2}\right) \left({2 \left({k+1}\right) + 1}\right)} 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 + \left({k+1}\right)^2$

We can now apply our induction hypothesis, obtaining:

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \sum_{i \mathop = 1}^{k+1} i^2\) \(=\) \(\displaystyle \) \(\displaystyle \frac{k \left({k + 1}\right) \left({2 k + 1}\right)} 6 + \left({k + 1}\right)^2\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \frac{k \left({k + 1}\right) \left({2 k + 1}\right) + 6 \left({k + 1}\right)^2} 6\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \frac{\left({k + 1}\right) \left({k \left({2 k + 1}\right) + 6 \left({k + 1}\right)}\right)} 6\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \frac{\left({k + 1}\right) \left({2 k^2 + 7 k + 6}\right)} 6\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \frac{\left({k + 1}\right) \left({k + 2}\right) \left({2 \left({k + 1}\right) + 1}\right)} 6\) \(\displaystyle \) \(\displaystyle \)                    

So $P \left({k}\right) \implies P \left({k+1}\right)$ 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 \left({n + 1}\right) \left({2 n + 1}\right)} 6$

$\blacksquare$


Proof 2

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

$\blacksquare$


Proof 3

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 \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle n^2\) \(=\) \(\displaystyle \) \(\displaystyle \frac {n^2 + n + n^2 - n} 2\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \frac {n \left({n+1}\right) + n \left({n-1}\right)} 2\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \frac {n \left({n+1}\right)} 2 + \frac{n \left({n-1}\right)} 2\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle T_n + T_{n-1}\) \(\displaystyle \) \(\displaystyle \)                    

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


Then:

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

$\blacksquare$


Proof 4

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 \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \) \(\displaystyle \sum_{i \mathop = 1}^n \left({\sum_{j \mathop = i}^n j}\right)\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \sum_{i \mathop = 1}^n \left( {\sum_{j \mathop = 1}^n j - \sum_{j \mathop = 1}^{i-1} j} \right)\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \sum_{i \mathop = 1}^n \left({\frac {n \left({n+1}\right)} 2 - \frac {i \left({i-1}\right)} 2}\right)\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle 2 \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \) \(\displaystyle n^2 \left({n+1}\right) - \sum_{i \mathop = 1}^n i^2 + \sum_{i \mathop = 1}^n i\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle 3 \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \) \(\displaystyle n^2 \left({n+1}\right) + \sum_{i \mathop = 1}^n i\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle 3 \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \) \(\displaystyle n^2 \left({n+1}\right) + \frac {n \left({n+1}\right)} 2\) \(\displaystyle \) \(\displaystyle \)          Closed Form for Triangular Numbers          
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle 6 \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \) \(\displaystyle 2 n^2 \left({n+1}\right) + n \left({n+1}\right)\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle n \left({n+1}\right) \left({2n+1}\right)\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \implies\) \(\displaystyle \) \(\displaystyle \sum_{i \mathop = 1}^n i^2\) \(=\) \(\displaystyle \) \(\displaystyle \frac {n \left({n+1}\right) \left({2n+1}\right)} 6\) \(\displaystyle \) \(\displaystyle \)                    

$\blacksquare$


Proof 5

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

On the other hand:

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \sum_{i \mathop = 1}^n \left({\left({i + 1}\right)^3 - i^3}\right)\) \(=\) \(\displaystyle \) \(\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\) \(\displaystyle \) \(\displaystyle \)          Definition of Summation          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({n + 1}\right)^3 - 1^3\) \(\displaystyle \) \(\displaystyle \)          Telescoping Series          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle n^3 + 3n^2 + 3n + 1 - 1\) \(\displaystyle \) \(\displaystyle \)          Binomial Theorem          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle n^3 + 3n^2 + 3n\) \(\displaystyle \) \(\displaystyle \)                    

Therefore:

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

Therefore:

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

$\blacksquare$


Historical Note

This result was documented by Āryabhaṭa in his work Āryabhaṭīya of 499 CE.


Sources