3
$\begingroup$

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!

$\endgroup$
2
  • 3
    $\begingroup$ 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$. $\endgroup$ Nov 1, 2017 at 17:53
  • $\begingroup$ 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/…. $\endgroup$ Nov 1, 2017 at 18:19

5 Answers 5

4
$\begingroup$

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.

$\endgroup$
2
3
$\begingroup$

Here's a proof without words:

enter image description here

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

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .