4
$\begingroup$

I've been asked to find the sum of the squares of the first $n$ natural numbers.

My initial thought was to just program a brute-force solution but I was wondering if there is a mathematical formula to come up with the answers.

I've made a table of all differences etc but I can't seem to find a suitable formula. How would I go about finding one, and is there even one?

$\endgroup$

closed as off-topic by David K, user91500, Behrouz Maleki, Rohan, user26857 Dec 17 '16 at 9:52

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user91500, Behrouz Maleki, Rohan
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Of course there is a formula. Try induction over $n$. $\endgroup$ – lattice May 31 '16 at 12:35
  • 1
    $\begingroup$ In Wikipedia, square pyramidal number. $\endgroup$ – peterwhy May 31 '16 at 12:36
  • 1
    $\begingroup$ Bernoulli's trick is always handy: Compute $\sum (i^3-(i-1)^3)$ in two ways. $\endgroup$ – lulu May 31 '16 at 12:36
  • 2
    $\begingroup$ Begin with $f(n)=an^3+bn^2+cn+d$ and find $a,b,c,d$ by setting $n=1,2,3,4$ and inserting the sum in each case. If you also consider $n=0$, you immediately get $d=0$. It is not difficult to solve the emerging linear system. $\endgroup$ – Peter May 31 '16 at 12:38
  • 1
    $\begingroup$ Possible duplicate of How to get to the formula for the sum of squares of first n numbers? $\endgroup$ – David K Dec 17 '16 at 1:52

10 Answers 10

8
$\begingroup$

I like visual proofs. In the following, the first three shapes pile together $1^1$, $2^2$, $3^2$, $4^2$ little cubes:

visual sum of squares

with similar visions in:

  • Claudi Alsina and Roger Nelsen, When Less is More: Visualizing Basic Inequalities (2009)
  • Roger B. Nelsen, Proofs without words 2. More exercises in visual thinking (2000)
  • Roger B. Nelsen, Proofs without words. Exercises in visual thinking (1993)

which I discuss in Unconventional mathematics books.

The three same basic shapes, sums of squares, add up to $n(n+1)(n+\frac{1}{2})$, hence the volume (a third) you are looking for is : $$\frac{n(n+1)(2n+1)}{6}\,.$$

Last comment: $\int x^p \sim \frac{x^{p+1}}{p+1}$, hence integration "adds" a degree. The case $p=-1$ is a bit different, but I'd argue the $\log$ is dimensionless, i.e. a variant of $0$-degree polynomials. Similarly, summing $p$-powers often leads to $p+1$-power formulae.

$\endgroup$
6
$\begingroup$

Hint

I assume you know that $\sum_{i=1}^ni=\frac{n(n+1)}2$. So, it is somewhat natural to expect $\sum_{i=1}^ni^2$ to be of the form $$f(n)=an^3+bn^2+cn+d$$ for some $a,b,c,d\in\Bbb{Q}$. (If you know calculus, this is related to the fact that $\int_0^xt^2dt=\frac{t^3}3+C$)

Now, you know $$f(0)=d=0$$ $$f(1)=a+b+c+d=1$$ $$f(2)=8a+4b+2c+d=5$$ $$f(3)=27a+9b+3c+d=14$$ In fact, these equations are enough to find $a,b,c,d$.(If you know linear algebra, this is a non-singular square matrix). You can play with these coeeficients to solve for $a,b,c,d$. When you did find $a,b,c,d$; you can prove that $f(n)$ indeed gives the some of first $n$ squares by showing $f(n)-f(n-1)=n^2$.

In fact, you can use this method to find the sum of cubes, or some of the fourth powers, or the sum of first powers, you only need to adjust the degree of the polynomial and the number of equations.

$\endgroup$
  • $\begingroup$ Personally, I like this one the best. Proof by induction doesn't tell us how to get the formula in the first plce $\endgroup$ – Yuriy S May 31 '16 at 13:17
  • $\begingroup$ This argument helps discover the formula, but doesn't prove it works for all $n$. Induction is a straightforward enough approach for that. Alternatively, if you could prove that the sum of $k^{th}$ powers is always a $k+1$ degree polynomial, you'd be done in general. I'd be interested to see an argument for this. $\endgroup$ – Zach Stone May 31 '16 at 13:42
  • 1
    $\begingroup$ @ZachStone $g(n)=f(n)-f(n-1)$ is a polynomial of degree $k$, and it gives $m^k$ for $m=1,2,\ldots,k+1$. Thus, $g(n)=n^k$ for all $n$. So, $f(n)$ is equal to the sum of the first $n$ $k$-th powers. $\endgroup$ – Emre May 31 '16 at 13:45
  • $\begingroup$ Ah, I see. That's clever. For the last step, it looks like you're using the fact that summing $g(n)$ results in a telescoping series that collapses to $f(n)$. That's the detail that makes the whole thing fit. $\endgroup$ – Zach Stone May 31 '16 at 13:56
  • $\begingroup$ Yes, in fact, that is no different than induction. But, intuitively telescoping sums makes a lot more sense than the abstract idea of induction to me. $\endgroup$ – Emre May 31 '16 at 13:57
3
$\begingroup$

Let $$B_n=1^2+2^2+..+n^2$$ $B_1=1, B_2=5, B_3=14, B_4=30, B_5=55, B_6=91$

Let $$A_n=1+2+..+n=\frac{n(n+1)}{2}$$ $$\frac{B_1}{A_1}=1, \frac{B_2}{A_2}=\frac{5}{3}, \frac{B_3}{A_3}=\frac{7}{3}, \frac{B_4}{A_4}=\frac{9}{3}, \frac{B_5}{A_5}=\frac{11}{3}, \frac{B_6}{A_6}=\frac{13}{3},..$$ Hypothesis: $$\frac{A_n}{B_n}=\frac{2n+1}3$$

It is proved by induction. Then $$B_n=A_n\frac{2n+1}{3}=\frac{n(n+1)(2n+1)}{6}$$

$\endgroup$
  • $\begingroup$ Pretty cool proof. $\endgroup$ – novice May 31 '16 at 13:55
3
$\begingroup$

If you know the method of finite differences, it can also be applied to this problem. Let $f(n)=\sum_{i=1}^n i^2$:

$$ \begin{array}{c|lcr} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & ... \\ \hline f(n) & 1 & 5 & 14 & 30 & 55 & 91 & 140 & ... \\ \nabla n & & 4 & 9 & 16 & 25 & 36 & 49 & ... \\ \nabla^2n & & & 5 & 7 & 9 & 11 & 13 & ... \\ \nabla^3 n & & & & 2 & 2 & 2 & 2 & ... \\ \end{array} $$

Once we see that there are constant differences, we know that a polynomial of the order of those constant differences will satisfy our sequence of numbers. In this case, the constant $2$'s correspond to the third level of differences, and therefore a polynomial of the form $g(n)=an^3+bn^2+cn+d$ will be the solution.

Using $g(1)$, $g(2)$, $g(3)$, and $g(4)$, the system of equations

$$ \left\{ \begin{array}{c} a+b+c+d=1 \\ 8a+4b+2c+d=5 \\ 27a+9b+3c+d=14 \\ 64a+16b+4c+d=30 \end{array} \right. $$

results (the same system that has shown up in previous answers), and your favorite method to solve for $a,b,c$ and $d$ can be applied. In the end, the formula that results is $$g(n)=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}$$

$\endgroup$
3
$\begingroup$

If we may assume to know that $$\sum_{k=1}^{n}k=\frac{n\left(n+1\right)}{2} $$ we can use the partial summation formula $$\sum_{k=1}^{n}k^{2}=\sum_{k=1}^{n}k\cdot k=n\sum_{k=1}^{n}k-\sum_{k=1}^{n-1}\left(\frac{k\left(k+1\right)}{2}\right)\left(k+1-k\right) $$ $$=\frac{n^{2}\left(n+1\right)}{2}-\frac{1}{2}\sum_{k=1}^{n-1}k^{2}-\frac{n\left(n-1\right)}{4} $$ so $$\frac{3}{2}\sum_{k=1}^{n}k^{2}=\frac{2n^{2}\left(n+1\right)-n\left(n+1\right)+2n^{2}}{4}\Rightarrow\sum_{k=1}^{n}k^{2}=\frac{n\left(n+1\right)\left(2n+1\right)}{6}.$$

$\endgroup$
2
$\begingroup$

$$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$

You can proof this by induction, for example.

$\endgroup$
1
$\begingroup$

$$\begin{align} \sum_{r=1}^n r^2&=\frac 14\sum_{r=1}^n(2r)^2\\ &=\frac 14\sum_{r=1}^n\binom {2r}2+\binom{2r+1}2\\ &=\frac 14\sum_{r=1}^{2n+1}\binom r2\\ &=\color{red}{\frac 14\binom{2n+2}3}\\ &=\frac 14\cdot \frac{(2n+2)(2n+1)(2n)}{1\cdot 2\cdot 3}\\ &=\color{red}{\frac 16 n(n+1)(2n+1)}\qquad\blacksquare\end{align}$$

$\endgroup$
0
$\begingroup$

Hint: try

$${n(n+1)(2n+1)\over 6}$$

Either by induction or by computing in two different ways $k^3=((k-1)+1)^3$ for $1\leq k\leq n+1$ and adding up

$\endgroup$
  • $\begingroup$ Done thanks a lot $\endgroup$ – marwalix May 31 '16 at 12:44
0
$\begingroup$

See this post where I explain an efficient method for finding such formulae (asymptotically much faster than finding and solving those linear equations that other answers mention). The linked post in fact contains the complete solution to this very question. Basically we know that any polynomial function $f$ can be expressed in the form:

$f(n) = \sum_{k=0}^\infty D^k(f)(0) \binom{n}{k}$ where $D$ is the forward-difference operator.

This is a finite sum and the number of terms is at most one more than the polynomial degree of $f$. Note that the reason it is easier than other methods is that binomial coefficients form a nicer basis than the monomials, since:

$D\left( \text{int $n$} \mapsto \binom{n}{k+1} \right) = \left( \text{int $n$} \mapsto \binom{n}{k} \right)$

In exactly the same manner as:

$\frac{d}{dx}(\frac{x^{k+1}}{(k+1)!}) = \frac{x^k}{k!}$

Thus the formula above (also known as Newton's formula) is nothing but the discrete version of Taylor series.

$\endgroup$
0
$\begingroup$

Here is a solution based upon formal power series. We proceed accordingly to this answer which provides the solution to the sum of $k$-th powers of the first $n$ numbers \begin{align*} \sum_{j=1}^nj^k \end{align*}

In the following we use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series. We also use the differential operator $D_x:=\frac{d}{dx}$.

We obtain \begin{align*} \sum_{j=0}^n j^2&=[x^n]\frac{1}{1-x}(xD_x)^2\frac{1}{1-x}\tag{1}\\ &=[x^n]\frac{x(1+x)}{(1-x)^4}\\ &=[x^n](x+x^2)\sum_{j=0}^{\infty}\binom{-4}{j}(-x)^{j}\tag{2}\\ &=\left([x^{n-1}]+[x^{n-2}]\right)\sum_{j=0}^{\infty}\binom{j+3}{3}x^j\tag{3}\\ &=\binom{n+2}{3}+\binom{n+1}{3}\\ &=\frac{1}{6}n(n+1)(2n+1) \end{align*}

Comment:

  • In (1) we apply the operator $\frac{1}{1-x}(xD_x)^2$ to $\frac{1}{1-x}$

  • In (2) we use the binomial series expansion

  • In (3) we use the linearity of the coefficient of operator, apply the formula \begin{align*} [x^{p-q}]A(x)=[x^p]x^qA(x) \end{align*} and use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q \end{align*}

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.