Prove $\sum_{b=0}^{n-1}b\binom{n+1-b}{2} = \binom{n+2}{4}$

Question

An equilateral triangle of side $n$ is divided into $n^2$ equilateral triangles of side $1$ such that each side of the congruent triangles is parallel to the original triangle. Find the number of parallelograms that can be formed by the segments.

The answer to this problem is $3 \binom{n+2}{4}$. I have a different solution than the intended one and arrived at the following sum: $$3\sum_{b=0}^{n-1}b\binom{n+1-b}{2}$$

Wolfram Alpha verifies that it is equal to $3\binom{n+2}{4}$, however I can't prove it. I tried pairing the terms, applying some identities, but failed.

Answer 1

I'll show bijectively that $$\sum_{b = 0}^{n-1} b \cdot \binom{n-1-b}{2} = \binom{n}{4}\,.$$

The right-hand side is clearly the number of ways to choose a subset of $4$ elements from $[n] = \{1,2,\ldots, n\}$. We can choose this by

• Choosing the second largest element and calling it $n - b$
• Choosing the largest element, for which we have $b$ choices.
• Choosing the two smallest elements from the set $[n-b-1]$ for which we have $\binom{n-1-b}{2}$ choices.

This gives the formula for the left-hand side.

Answer 2

Marcus M has given a very nice combinatorial proof, which in general I prefer. Here’s a computational proof, in case you’re more comfortable with that approach.

$$\begin{align*} \sum_{b=0}^{n-1}b\binom{n-1-b}2&\overset{(0)}=\sum_{k=0}^{n-1}(n-1-k)\binom{k}2\\ &=n\sum_{k=0}^{n-1}\binom{k}2-\sum_{k=0}^{n-1}(k+1)\binom{k}2\\ &\overset{(1)}=n\binom{n}3-3\sum_{k=0}^{n-1}\binom{k+1}3\\ &=n\binom{n}3-3\sum_{k=1}^n\binom{k}3\\ &\overset{(1)}=n\binom{n}3-3\binom{n+1}4\\ &=\frac{n^2(n-1)(n-2)}6-\frac{(n+1)n(n-1)(n-2)}8\\ &=\frac{n(n-1)(n-2)}2\left(\frac{n}3-\frac{n+1}4\right)\\ &=\frac{n(n-1)(n-2)}2\cdot\frac{n-3}{12}\\ &=\frac{n(n-1)(n-2)(n-3)}{24}\\ &=\binom{n}4\;. \end{align*}$$

At $(0)$ I substituted $k=n-1-b$, and at $(1)$ I used the hockey stick identity.