# Prove that $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$ without using induction.

I have to deduce the following formula $$1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6},$$ while using the given formula $$\binom{k}{0}+\binom{k+1}{1}+\cdots+\binom{k+r}{r}=\binom{k+r+1}{r}$$

I tried to find values for $k$, such that $\binom{k}{0}=1^2$ etc. but that didn't work. Does anybody have a push in the right direction? Thanks!

• If you use symmetry to rewrite as $\binom{k}{k} + \binom{k+1}{k} + \cdots + \binom{k+r}{k} = \binom{k+r+1}{k+1}$, then see what you get with $k=2$. Nov 1, 2017 at 17:53
• In order to exploit the hockey stick identity it is enough to notice that $n^2=2\binom{n}{2}+\binom{n}{1}$. A colorful geometric proof can be found on ckrao.wordpress.com/2012/03/14/…. Nov 1, 2017 at 18:19

Using your identity, we can write $$\binom{k}{k} + \binom{k+1}{k} + \cdots + \binom{k+r}{k} = \binom{k+r+1}{k+1}$$ and take $k=2$ to give $$\binom{2}{2} + \binom{3}{2} + \cdots + \binom{r+2}{2} = \binom{r+3}{3}$$ but we know that $\binom{k}{2} = \frac{k(k-1)}{2}$, so \begin{align}\binom{r+3}{3} &= \sum_{i=0}^r \binom{i+2}{2} \\ \frac{(r+3)(r+2)(r+1)}{6} &= \sum_{i=0}^r \frac{(i+1)(i+2)}{2} \\ &= \sum_{i=0}^r \left(\frac{1}{2}i^2 + \frac{3}{2}i+1\right) \\ &= \frac{1}{2}\sum_{i=1}^ri^2 + \frac{3}{2}\frac{r(r+1)}{2}+r+1 \end{align} from which the desired identity easily follows.

• math.stackexchange.com/questions/241760/… Nov 1, 2017 at 18:12
• @GuyFsone: the main concern of the OP does not seem to be how to devise a geometric proof, but rather how to be able to apply the hockey stick identity. Nov 1, 2017 at 18:20

Here's a proof without words:

https://www.maa.org/sites/default/files/Siu15722.pdf

When I was (much) younger I wanted to find the area of a segment of parabola so I needed the sum of the squares and I found the formula by myself in this way.

Inspired by the famous $1+2+\ldots+n=\dfrac{n(n+1)}{2}$

I supposed that the sum of the square could be a third degree polynomial in $n$

$P(n)=an^3+bn^2+cn$

Then I plugged the first $3$ values for $n$ getting

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

which gives $a=\frac13;\;b=\frac12;\;c=\frac16$

and therefore

$$P(n)=\frac13 n^3+\frac12 n^2+\frac16 n=\frac16 (2 n^3+3 n^2+n)=\frac16 n(n+1)(2n+1)$$

It is not elegant, but in 1977 there was no wikipedia :)

Hope it can be useful

(Not using the combinatorial identity but without induction)

You can start saying that $$(k+1)^{3}-k^3=3k^2+3k+1$$

then you take the sum in both sides to get:

$$\sum_{k=1}^{n}\bigg((k+1)^{3}-k^3\bigg)=\sum_{k=1}^{n}\big(3k^2+3k+1\big)$$

The LHS is a telescopic sum and RHS will give you the sum you are looking for:

$$(n+1)^3-1^3=\sum_{k=1}^{n}\bigg((k+1)^{3}-k^3\bigg)=3\sum_{k=1}^{n}k^2+3\sum_{k=1}^{n}k+\sum_{k=1}^{n}1 =3\sum_{k=1}^{n}k^2+3\frac{n(n+1)}{2}+n$$

and this implies:

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

You can compute $\sum_{k=1}^{n}k$ without induction by saying that $$(k+1)^{2}-k^{2}=2k+1$$ and repeat the last argument.

I think that this one is the easyest one:

$${n-1\choose 2} +{n-2\choose 2} + ...+{2\choose 2} = {n\choose 3}$$

Why is this valued? Think of the ways you can take 3 elements from the set with n elements.