9
$\begingroup$

While thinking about another question I found out that this equality might be useful there: $$n\cdot 1 + (n-1)\cdot 2 + \dots + 2\cdot (n-1) + 1\cdot n = \frac{n(n+1)(n+2)}6$$ To rewrite it in a more compact way: $$\sum_{k=1}^n k(n+1-k)=\frac{n(n+1)(n+2)}6.$$

This equality is relatively easy to prove: $$\sum_{k=1}^n k(n+1-k)= (n+1)\sum_{k=1}^n k - \sum_{k=1}^n k^2 = (n+1) \frac{n(n+1)}2 - \frac{n(n+1)(2n+1)}6 = n(n+1) \left(\frac{n+1}2-\frac{2n+1}6\right) = n(n+1)\frac{3(n+1)-(2n+1)}6 = \frac{n(n+1)(n+2)}6.$$ (We only used the known formulas for the sum of the first $n$ squares and the sum of the first $n$ numbers.)

Are there some other nice proofs of this equality? (Induction, combinatorial arguments, visual proofs, ...)


EDIT: Now I found another question which asks about the same identity: Combinatorial interpretation of a sum identity: $\sum_{k=1}^n(k-1)(n-k)=\binom{n}{3}$ (I have tried to search before posting. But the answers posted here so far gave me some new ideas for good keywords to search which lead me to finding that question.) The questions are, in my opinion, not exact duplicates since the other question asks specifically about combinatorial proofs and my question does not have that restriction. But I agree that this is a very minor distinction. In any case, if you think that one of them should be closed as a duplicate, then you can vote to close. I will refrain from voting to close/reopen on this question. (If one of the two questions is voted to be a duplicate of the other one, they probably cannot be merged, since the summation variables are off by one.)

$\endgroup$
  • 5
    $\begingroup$ Generating functions? Coefficient of $x^{n+1}$ in $\left(\sum\limits_{n=1}^{\infty} nx^{n}\right)^2$ $\endgroup$ – sciona Jan 21 '15 at 14:33
  • 1
    $\begingroup$ Here is another post about the same formula. $\endgroup$ – Martin Sleziak Oct 2 '15 at 17:31
10
$\begingroup$

Let us choose three numbers from $\{0,1,2,\ldots, n+1\}$, beginning with the middle one, which has to be some $k\in \{1,\ldots,n\}$. We then have $k$ choices for the smallest and $n+1-k$ choices for the largest of the three. It follows that $${n+2\choose3}=\sum_{k=1}^n k(n+1-k)\ .$$

$\endgroup$
  • 2
    $\begingroup$ Straight to the point! +1 $\endgroup$ – user2345215 Jan 21 '15 at 15:02
5
$\begingroup$

I think of this as the "twelve days of Christmas equality", because if $n = 12$ then we get $1 \times 12 + 2 \times 11 + \cdots + 12 \times 1 = {14 \choose 3}$ and both sides represent the number of gifts which are given in the song "The Twelve Days of Christmas". (This happens to be 364, one less than the number of days in a year.)

Here's a combinatorial proof of that equality, which I have previously written about at my blog. As I wrote there, let's try to prove the identity $\sum_{j=2}^{n+1} (j-1)(n+2-j) = {n+2 \choose 3}$, which differs from your equality by a change of index. To do this, we count subsets of the set $\{ 1, 2, \ldots, n+2 \}$ of size 3. We can write each such subset as $\{ x, y, z \}$ where we require $x < y < z.$ Then we’ll count these subsets according to the difference $z - x$. To construct such a set with $z - x = j$ we must:

  • choose $x$. $x$ must be between $1$ and $n+2-j$ inclusive, so there are $n+2-j$ possible choices.
  • choose $y$. $y$ must be between $x$ and $z=x+j$ exclusive, so there are $j-1$ possible choices.

At this point $z$ is fixed. So there are $(j-1)(n+2-j)$ ways to choose a $3$-set with $z - x = j$; summing over the possible values of $j$ gives the desired identity.

$\endgroup$
  • 1
    $\begingroup$ I guess more-or-less the same argument could be reformulated like this. Let us start by choosing $y$. We only can choose $2, 3, \dots, n+1$. To make the notation the same as in your sum, let us denote $j=y$. If $y$ is chosen, we can choose any of elements on the left for $x$, which gives $(j-1)$ possibilities. We can choose any of the elements on the right for $z$, which gives $(n+2-j)$ possibilities. Together we have $\sum_{j=2}^{n+1} (j-1)(n+2-j)$. BTW +1 for the nice combinatorial argument and thanks for the link to your blog. $\endgroup$ – Martin Sleziak Jan 21 '15 at 14:46
2
$\begingroup$

A convolution is always a good way. Since: $$ \sum_{k\geq 0} k z^k = \frac{z}{(1-z)^2}, \tag{1}$$ we have: $$\begin{eqnarray*}\sum_{k=1}^{n}k(n+1-k) = \sum_{k=0}^{n+1}k(n+1-k) &=& [z^{n+1}]\frac{z^2}{(1-z)^4}\\&=&[z^n]\frac{z}{(1-z)^4}\tag{2}\end{eqnarray*}$$ and the claim follows from: $$ \sum_{k\geq 0}\binom{k+2}{3}z^k = \frac{z}{(1-z)^4}.\tag{3}$$

$\endgroup$
  • $\begingroup$ I suppose the notation $[z^k]f(z)$ means: "the coefficient of $z^k$ in the power series $f(z)$", right? $\endgroup$ – Martin Sleziak Jan 21 '15 at 14:49
  • 2
    $\begingroup$ @MartinSleziak: yes, it is the standard notation in analytic combinatorics. I am just borrowing it from Wilf or Flajolet. $\endgroup$ – Jack D'Aurizio Jan 21 '15 at 14:52
1
$\begingroup$

Induction is pretty straighforward: \begin{align*}\sum_{k=1}^{n+1}&k(n+2-k)-\sum_{k=1}^n k(n+1-k)=(n+1)+\sum_{k=1}^n k\cdot 1=\sum_{k=1}^{n+1} k\\&=\frac{(n+1)(n+2)}2=\frac{(n+1)(n+2)(n+3)}6-\frac{n(n+1)(n+2)}6\end{align*}

$\endgroup$
1
$\begingroup$

Here is another solution. $$n\cdot 1+(n-1)\cdot2+\ldots1\cdot n=\\ (n+(n-1)+\ldots +1)+((n-1)+(n-2)+\ldots+1)+\ldots+1=\\ \sum_{i=1}^ni+\sum_{i=1}^{n-1}i+\ldots+1=\\ \frac{(n+1)n}{2}+\frac{n(n-1)}{2}+\ldots +\frac{2\cdot 1}{2}.$$ Now, this sum is equal $$\frac{(n+2)(n+1)n}{6}$$ by a straightforward induction.

$\endgroup$
  • $\begingroup$ Your equality can be seen also as $\binom{n+1}2+\binom{n}2+\dots+\binom22=\binom{n+2}3$, which can be a bit generalized to what some people call hockey-stick identity. See, for example, article on AoPS Wiki or this post (and some of the posts linked to it). $\endgroup$ – Martin Sleziak Jan 22 '15 at 8:13
  • 1
    $\begingroup$ True, thank you for pointinig it out. $\endgroup$ – Ofir Schnabel Jan 22 '15 at 8:14

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.