Derive Closed form sum of N^2

Can anyone explain to me how you would derive this ? I have this question asked in a CS class and can’t figure out how to derive it. it has to be derived as you would with sum of N

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

Solutions Collecting From Web of "Derive Closed form sum of N^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}$$

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

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,

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

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

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.