Derive Closed form sum of N^2

Question

Can anyone explain to me how you would derive this equation? $$\sum_{i=0}^{N} i^{2} = \frac{2N^{3} + 3N^{2} + N}{6}$$

In my CS class, I was told that it can be derived as you would with the sum of N

$$\sum_{i=0}^{N} i = \frac{N(N + 1)}{2}$$

ex

1 2    3  ......  N 
N N-1  N-2    ....1 
---------------------
N+1 + N+1 + .... N+1 = N(N+1) SINCE THIS ADDITION IS 2 * THIS SUM THEN CLOSED FORM IS N(N+1)/ 2

Answer 1

The result is a polynomial of third degree $ak^3+bk^2+cx+d$. Collect four examples $k=1,2,3,4$, get the coefficients $a,b,c,d$ and use proof by induction.

Good luck,

Answer 2

Okay, someone will post a method of common differences soon enough, so let's take a new approach. Combinatorics. Particularly because I recently learnt this myself.

Consider this: How many ways can I choose ordered triples $(a,b,c)$ from $0\le a,b\lt c\le n$?

For fixed $c$ this can be done in $c^2$ ways, because $a$ and $b$ can independently take values in the set $\{0,1,2,\cdots,c-1\}$. Since $c$ can take any value between $1$ and $n$, the total number of ways is $$1^2+2^2+\cdots+n^2$$

Now to find this number combinatorically!

There are $C(n+1,2)$ triples of the form $(a,a,c)$. To form triples of the form $(a,b,c)$ with $a\ne b$ We can select $a,b,c$ in $C(n+1,3)$ ways, and to each way there are two triples, $(a,b,c)$ and $(b,a,c)$.

Thus we can conclude that $$1^2+2^2+\cdots+n^2 = {n+1\choose 2}+2{n+1\choose 3}$$

Answer 3

Here's my favourite trick for $\sum_{k=1}^N k^2$. Note that $(k+1)^3 - (k-1)^3 = 6 k^2 + 2$. So $$\sum_{k=1}^N \left((k+1)^3 - (k-1)^3\right) = \sum_{k=1}^N (6 k^2+2)$$ Now if you look closer at the sum on the left, you see a lot of cancellations: all the cubes from $2^3$ to $(N+1)^3$ are there with $+$ signs, and all those from $0^3$ to $(N-1)^3$ are there with $-$ signs. All that's left after cancellation is $N^3 + (N+1)^3 - 0^3 - 1^3 = N^3 + (N+1)^3 - 1$. On the right, we have $6 \sum_{k=1}^N k^2+ \sum_{k=1}^N 2 = 2 N + 6 \sum_{k=1}^N k^2$. Subtract $2N$ from both sides, divide by $6$ and simplify...

You can get a formula for $\sum_{k=1}^N k^3$ similarly, starting with $(k+1)^4 - (k-1)^4 = 8 k^3 + 8 k$.

Answer 4

From the description below it is easy to see: $$\sum\limits_{k=1}^{n}k^2 = n\sum\limits_{k=1}^{n}k - \sum\limits_{k=1}^{n-1}\sum\limits_{l= 1}^{k}l= \\= n\frac{n(n+1)}{2} - \frac12\sum\limits_{k=1}^{n-1}k(k+1) =\\=n\frac{n(n+1)}{2} - \frac12\frac{n(n-1)}{2} - \frac12\sum\limits_{k=1}^{n}k^2 + \frac{n^2}{2}\\\Downarrow \text{multiply by 2 both sides}\\3\sum\limits_{k=1}^{n}k^2 = n^3 + n^2 - \frac{n^2}{2} + \frac{n}{2} +n^2 =\\= n^3 + \frac{3n^2}{2} + \frac{n}{2}.$$ Eventually, $$\sum_{1}^{n}k^2 = \frac{n^3}{3}+ \frac{n^2}{2} + \frac{n}{6}.$$

---

Visual description

$$\sum_{1}^{n}k^2 = \begin{pmatrix} 1 & 2 & 3 & 4 & \cdots & n\\ 0 & 2 & 3 & 4 & \cdots & n\\ 0 & 0 & 3 & 4 & \cdots & n\\ 0 & 0 & 0 & 4 & \cdots & n\\ \vdots & \vdots & \vdots & \vdots & \vdots & n \\ 0 & 0 & 0 & 0 & \cdots & n \end{pmatrix}_\sum = \\ =\begin{pmatrix} 1 & 2 & 3 & 4 & \cdots & n \\ 1 & 2 & 3 & 4 & \cdots & n \\ 1 & 2 & 3 & 4 & \cdots & n \\ & & & \vdots & \\ 1 & 2 & 3 & 4 & \cdots & n \\ \end{pmatrix}_\sum - \begin{pmatrix} 0 & 0 & 0 & 0 & \cdots & 0 \\ 1 & 0 & 0 & 0 & \cdots & 0 \\ 1 & 2 & 0 & 0 & \cdots & 0 \\ 1 & 2 & 3 & 0 & \cdots & 0 \\ & & & \vdots & \\ 1 & 2 & 3 & 4 & \cdots & n \\ \end{pmatrix}_\sum$$

Answer 5

This is similar to another answer, but I used consecutive terms in my derivation. I am taking these sums from 1 to N.

Once you know what the SUM(n) is, you can reduce SUM(n^2) to an algebraic expression containing the of SUM(n), where SUM(n) = N(N+1)/2. Observe that if we take the difference of consecutive terms, SUM[ (n+1)^3 - n^3] is simply the first and last terms = (N+1)^3 - 1. If we expand (n+1)^3 - n^3 we get 3n^2 + 3n + 1. So we can get an expression for SUM(n^2). 3SUM(n^2) + 3(SUM(n)) + SUM(1) = (N+1)^3 - 1. So 3SUM(n^2) + 3(N+1)N/2 + N = N^3 + 3N^2 + 3N. Just solve for SUM(n^2). SUM(n^2) = (2N^3 + 3N^2 + N)/6

You can expand SUM[(n+1)^4 - n^4] to get SUM(n^3) in a similar way once you know SUM(n^2) and SUM(n), and on and on to get any SUM of n raised to any power.

Answer 6

By educated guess, the sum will be a polynomial of the third degree in $n$ (because the first order difference is a quadratic polynomial) such that

• there is no constant coefficient (no term $\to0$);

• the leading coefficient is $\frac13$, as for an antiderivative (or because $(n+1)^3-n^3=3n^2+$ lower degree terms);

• the coefficient of the quadratic term is $\frac12$.

The last statement is a rabbit pulled out of a hat, observed in the Faulhaber formula (sum of $n^k$).

Then

$$S_n=\frac{n^3}3+\frac{n^2}2+an.$$

From

$$S_1=1=\frac13+\frac12+a,$$ we deduce $$a=\frac16.$$

---

You can avoid the rabbit by solving

$$S_n=\frac{n^3}3+an^2+bn$$for $S_1=1$ and $S_2=5$.