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!
 A: 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.
A: Here's a proof without words: 

https://www.maa.org/sites/default/files/Siu15722.pdf
A: 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
A: (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. 
A: 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. 
