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$
  • 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$ – Daniel Schepler Nov 1 '17 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$ – Jack D'Aurizio Nov 1 '17 at 18:19
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$
3
$\begingroup$

Here's a proof without words:

enter image description here

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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