# How to prove ${n+2 \choose 3}=1\cdot n + 2 \cdot (n - 1) + \ldots + n \cdot 1$?

I saw this problem as an exercise in Combinatorial Identities :-

Prove that $${n+2 \choose 3}=1\cdot n + 2 \cdot (n - 1) + \ldots + n \cdot 1\,.$$

After giving some time to this, I think that it is quite similar to the identity :-

$${n \choose k} = {n - 1 \choose k - 1} + {n - 1 \choose k}$$

(Note that I am still not sure whether we can use that identity or not , I can also guess we can use Vandermonde's Identity here) .

I suggest proving it combinatorially. $$\binom{n+2}3$$ is the number of $$3$$-element subsets of the set $$[n+2]=\{1,2,\ldots,n+2\}$$. We can classify those sets by their middle elements: let $$\mathscr{A}_k$$ be the family of all $$3$$-element subsets of $$[n+2]$$ of the form $$\{j,k,\ell\}$$, where $$j; clearly

$$\binom{n+2}3=\sum_k|\mathscr{A}_k|\;.$$

Now prove that $$|\mathscr{A}_k|=(k-1)(n+2-k)$$ and determine the range of possible values of $$k$$ to complete the proof.

• thanks for the suggestion , but right now i am seeking an algebraical proof . May 1, 2020 at 15:35

Both are equal to the number of ways of selecting three numbers from $$1, \ldots, n+2$$ : the first one by definition, the second by choosing the middle number, say $$i+1$$, and then by choosing one of the $$i$$ available "to the left" to be the smaller one, and one of the $$(n+2)-(i+1)=n+1-i$$ available "to the right" to be the bigger one.

I am sure this identity has been proven here. I can't find it. Note that $$\sum_{k=0}^m\,\binom{k}{r}\,\binom{m-k}{s}=\binom{m+1}{r+s+1}\tag{*}$$ for every integers $$m,r,s$$ with $$0\leq r,s\leq m$$. A combinatorial proof is to count the number of $$(r+s+1)$$-subsets of $$\{0,1,2,\ldots,m\}$$. Clearly, there are $$\displaystyle\binom{m+1}{r+s+1}$$ such subsets.

For $$k=0,1,2,\ldots,m$$, there are precisely $$\displaystyle\binom{k}{r}\,\binom{m-k}{s}$$ subsets of sizer $$r+s+1$$ such that $$k$$ is the $$(r+1)$$-st smallest element of these sets. This proves (*). Now, the OP's problem is when $$m:=n+1$$, $$r:=1$$, and $$s:=1$$.

An algebraic proof of (*) can be seen by considering $$f(x):=\sum_{k=r}^\infty\,\binom{k}{r}x^{k-r}(1+x)^{m-k}=(1+x)^{m-r}\,\sum_{k=r}^\infty\,\binom{k}{r}\,\left(\frac{x}{1+x}\right)^{k-r}\,.$$ Thus, \begin{align}f(x)&=(1+x)^{m-r}\,\sum_{k=0}^\infty\,\binom{k+r}{r}\,\left(\frac{x}{1+x}\right)^k \\&=(1+x)^{m-r}\,\left(1-\frac{x}{1+x}\right)^{-r-1}=(1+x)^{m+1}\,.\end{align} For each integer $$t\geq 0$$, let $$[x^t]\,g(x)$$ denote the coefficient of $$x^t$$ in a polynomial $$g(x)$$. Then, $$\sum_{k=0}^m\,\binom{k}{r}\,\binom{m-k}{m-k-s}=[x^{m-r-s}]\,f(x)=[x^{m-r-s}]\,(1+x)^{m+1}\,.$$ Ergo, $$\sum_{k=0}^m\,\binom{k}{r}\,\binom{m-k}{s}=\sum_{k=0}^m\,\binom{k}{r}\,\binom{m-k}{m-k-s}=\binom{m+1}{m-r-s}=\binom{m+1}{r+s+1}\,.$$

Edit. I found a combinatorial proof of (*) in this old link. Analytic proofs of (*) are also given here. Algebraic proofs of (*) can be found here.

$$\sum_{k=1}^n k(n+1-k)=(n+1)\sum_{k=1}^nk-\sum_{k=1}^nk^2$$Now apply the identities$$\sum_{k=1}^nk=\frac12n(n+1)\qquad\sum_{k=1}^nk^2=\frac16n(n+1)(2n+1)$$and simplify the result.

We are trying to show that $$1\!\cdot\!n \, + \, 2\!\cdot\!(n - 1)\, + \, \ldots \, + \, n\!\cdot\!1\ = {n+2 \choose 3}$$ Peter Foreman wrote the left hand side as $$\sum_{k=1}^n k(n-k+1)$$ Another way to write the left hand side is $$\sum_{j=1}^n\sum_{k=1}^j k$$ The left hand side usually comes up as a summation nested within a summation. For example, on the first day of Christmas you get 1 gift; on the second day, you get $$1+2$$ gifts; on the 3rd day, $$1+2+3$$ gifts; .... $$\sum_{j=1}^{12} \sum_{k=1}^j k = \binom{12+2}{3} = 364$$

The Hockey Stick Identity is usually given as $$\sum_{i=r}^{m} \binom{i}{r} = \binom{m+1}{r+1}$$ But I have found this equivalent version useful because the summation starts at $$k=1$$ and goes to $$n = m - r +1$$: $$\sum_{k=1}^{n} \binom{k+r-1}{r} = \binom{n+r}{r+1}$$ For $$r=1$$ $$\sum_{k=1}^{n} \binom{k}{1} = \binom{n+1}{2}$$ For $$r=2$$ $$\sum_{j=1}^{n} \binom{j+1}{2} = \binom{n+2}{3}$$ So, \begin{align*} 1\!\cdot\!n \, + \, 2\!\cdot\!(n - 1)\, + \, \ldots \, + \, n\!\cdot\!1 = \sum_{j=1}^n\sum_{k=1}^j k\ &= \sum_{j=1}^n\sum_{k=1}^j \binom{k}{1}\\ &= \sum_{j=1}^n \binom{j+1}{2}\\ &= \binom{n+2}{3} \end{align*} This answers the question, but the pattern continues.

For $$r=3$$ $$\sum_{i=1}^{n} \binom{i+2}{3} = \binom{n+3}{4}$$ so $$\sum_{i=1}^{n}\sum_{j=1}^i\sum_{k=1}^j k\ = \binom{n+3}{4}$$

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Upon the inductive step, your RHS becomes

$$1(n+1) + 2(n) + \dots + n(2) + (n+1)1$$

$$= 1(n) + 2(n-1) + \dots + n(1) + \sum_{i=1}^{n+1} i$$

$$= \binom{n+2}{3} + \binom{n+2}{2}$$

$$= \binom{n+3}{3}$$

I think one must "emphasize" the steps in a proof by induction. I don't know how much I can do this for a reader. My try:

The satatement is the following: $$P(n): {n+2\choose3}=1.n+2.(n-1)+...+(n-1).2+n.1 \;\text{where}\;\; n\geq1.$$

For $$n=1$$, $$P(1)$$ is true, because $${1+2\choose3}=1.$$

Assume that for $$n$$, the statement $$P(n)$$ is true.

We must prove the statement for $$n+1$$, that is, we must prove that $$P(n+1)$$ is true:

$$\large\begin{array} .{(n+1)+2\choose 3}&={n+3\choose 3}\\ &={n+2\choose 3}+{n+2\choose 2}\hspace{0.5cm}\text{(By Pascal's triangle main property)}\\ &=1.n+2.(n-1)+...+(n-1).2+n.1+\frac{(n+2)(n+1)}{2}\hspace{1cm}(*)\\ &=\sum_{i=1}^{n}i(n+1-i)+\sum_{i=1}^{n+1}i\hspace{1cm}(**)\\ &=\sum_{i=1}^{n}i(n+1-i)+\sum_{i=1}^{n}i+(n+1)\;\text{(Separating one term...)}\\ &=\sum_{i=1}^{n}(i(n+1-i)+i)+(n+1).1\;\text{(Combining the two sums...)}\\ &=\sum_{i=1}^{n}i(n+1-i+1)+(n+1).1\\ &=\sum_{i=1}^{n}i(n+2-i)+(n+1).1\\ &=1.(n+1)+2.n+...+(n-1).3+n.2+(n+1).1\\ \end{array}$$ Hence $$P(n+1)$$ is true. Therefore, $$P(n)$$ is true for all $$n\geq 1$$ by induction.

Explanation of $$(*)$$ and $$(**)$$: $${n+2\choose 2}=\frac{(n+2)(n+1)}{2}$$ by definition of combination, but $$\sum_{i=1}^{n+1}i=\frac{(n+2)(n+1)}{2}$$ by Gauss sum.