Proof that $\binom{n + 3}{4} = n + 3 \binom{n + 2}{4} - 3 \binom{n + 1}{4} + \binom{n}{4}$.

Question

I was trying to count the number of equilateral triangles with vertices in an regular triangular array of points with n rows. After putting the first few rows into OEIS, I saw that this was described by A000332: $\binom{n}{4} = n(n-1)(n-2)(n-3)/24$.

A000332 has the comment:

Also the number of equilateral triangles with vertices in an equilateral triangular array of points with n rows (offset 1), with any orientation.

The linked solution is insightful, but the proof is very mechanical.

I tried to write an inductive proof, but I'm unable to come up with a nice way to prove the final identity (in particular for $n \geq 4$):

$$\binom{n + 3}{4} = n + 3 \binom{n + 2}{4} - 3 \binom{n + 1}{4} + \binom{n}{4}$$.

Wolfram|Alpha admits that these are indeed equal, and this could certainly be shown by writing everything as a polynomial.

However, I was hoping to find some nice combinatorial identities that give some intuition as to why this equality holds.

Answer 1

The identity is equivalent to \begin{align*} n&=\binom{3}{0}\binom{n + 3}{n-1}-\binom{3}{1} \binom{n + 2}{n-2} + \binom{3}{2}\binom{n + 1}{n-3} - \binom{3}{3}\binom{n}{n-4}\\ &=\sum_{k=0}^3 (-1)^k\binom{3}{k}\binom{(n-k)+3}{(n-k)-1}=[x^n](1-x)^3\cdot \frac{x}{(1-x)^5}=[x^{n+1}]\frac{1}{(1-x)^2} \end{align*} which holds.

P.S. Note that by replacing $3$ with $m$, we get $$\sum_{k=0}^m (-1)^k\binom{m}{k}\binom{(n-k)+m}{(n-k)-1}=[x^n](1-x)^m\cdot \frac{x}{(1-x)^{m+2}}=[x^{n+1}]\frac{1}{(1-x)^2}=n.$$

Answer 2

This is calculus of finite differences: $$\binom{n+1}2-\binom{n}2=\binom{n}1=n,$$ $$\binom{n+1}3-\binom{n}3=\binom{n}2,$$ $$\binom{n+1}4-\binom{n}4=\binom{n}3,$$ etc. Then $$n=\binom{n+1}2-\binom{n}2 =\left(\binom{n+2}3-\binom{n+1}3\right) -\left(\binom{n+1}3-\binom{n}3\right) =\binom{n+2}3-2\binom{n+1}3+\binom{n}3 =\left(\binom{n+3}4-\binom{n+2}4\right) -2\left(\binom{n+2}4-\binom{n+1}4\right) +\left(\binom{n+1}4-\binom{n}4\right) =\binom{n+3}4-3\binom{n+2}4+3\binom{n+1}4-\binom{n}4 $$ etc.

Answer 3

If you're looking for a more visual understanding of this, try drawing Pascal's triangle. For $0 \le r < s \le n$, consider $n \choose r$, $n \choose s$ and $n+(s-r) \choose s$. These three elements form the vertices of an equilateral triangle within Pascal's triangle.

Each of these vertices can be related to the elements along the opposite edge of the equilateral triangle. First, observe that $n+(s-r) \choose s$ is the convolution of the elements from $n \choose r$ through $n \choose s$ with the binomial coefficients ${s-r \choose 0}, {s-r \choose 1}, \ldots, {s-r \choose s-r}$; this follows directly from the construction of Pascal's triangle. For example, $10 = 1\cdot1 + 2\cdot3 + 1\cdot3$, for the same reason that $10$ is the sum of the two numbers above it ($10=4+6$):

$$\begin{matrix} &&&&&1\\ &&&&1&&1\\ &&&1&&2&&1\\ &&\bf\color{red}1&&\bf\color{red}3&&\bf\color{red}3&&1\\ &1&&4&&6&&4&&1\\ 1&&5&&\bf\color{red}{10}&&10&&5&&1\\ \end{matrix}$$

In your case, we're looking at the same relationship flipped on its side, as it were. Here we have $3 = 1\cdot10 - 2\cdot4 + 1\cdot1$, for the same reason that $3$ is the difference of the numbers below and beside it ($3 = 6-3$):

$$\begin{matrix} &&&&&1\\ &&&&1&&1\\ &&&1&&2&&1\\ &&\bf\color{red}1&&3&&\bf\color{red}3&&1\\ &1&&\bf\color{red}4&&6&&4&&1\\ 1&&5&&\bf\color{red}{10}&&10&&5&&1\\ \end{matrix}$$

Answer 4

$$\begin{align} \binom {n+3}4-3\binom {n+2}4+3\binom {n+1}4-\binom n4 &=\sum_{r=0}^3(-1)^{r+1}\binom 3r\binom {n+r}4\\ &=\sum_{r=0}^3(-1)^{r+1}\binom 3r\binom {n+r}{n+r-4}\\ &=\sum_{r=0}^3(-1)^{r+1}\binom 3r (-1)^{n+r-4}\binom {-5}{n+r-4}\tag{*}\\ &=(-1)^{n-3}\sum_{r=0}^3\binom 3{3-r}\binom {-5}{n+r-4}\\ &=(-1)^{n-1}\binom {-2}{n-1}\tag{**}\\ &=(-1)^{n-1}\cdot (-1)^{n-1}\binom n{n-1}\tag{*}\\ &=\binom n1\\ &=n\\\\ \binom {n+3}4&=n+3\binom {n+2}4-3\binom {n+1}4+\binom n4\;\color{red}\blacksquare \end{align}$$

*using upper negation
**using the Vandermonde Identity

Answer 5

Here is a combinatorial proof, with generalization. Let $m$, $n$, and $r$ be non-negative integers such that $m\leq n$. Consider $(m+r)$-subsets of the set $S=\{1,2,\ldots,n,n+1,n+2,\ldots,n+r\}$ which contain all numbers $n+1$, $n+2$, $\ldots$, $n+r$. Such a subset must be of the form $V\cup \{n+1,n+2,\ldots,n+r\}$ with $V\subseteq \{1,2,\ldots,n\}$ having $m$ elements. So there are $\binom{n}{m}$ possible subsets of this form. We now count the number of these subsets in a different way, using PIE.

Let $T_s$ denote the set of $s$-subsets of $T=\{n+1,n+2,\ldots,n+r\}$. Let $E_A$ denote the set of $(m+r)$-subsets $U$ of $S$ such that $A$ does not intersect $U$. Let $\mathcal{C}$ be the set of all $(m+r)$-subsets of $S$. Observe that $\mathcal{C}\setminus \bigcup_{k=1}^r E_{\{n+k\}}$ is the set composed by all $(m+r)$-subsets of $S$ which contain $n+1$, $n+2$, $\ldots$, $n+r$. By PIE, $$\left|\mathcal{C}\setminus \bigcup_{k=1}^rE_{\{n+k\}}\right|=\sum_{s=0}^r(-1)^s\sum_{A\in T_s}\left|E_A\right|.$$ Since $|E_A|=\binom{n+r-s}{m+r}$ and $|T_s|=\binom{r}{s}$, we get $$\binom{n}{m}=\left|\mathcal{C}\setminus \bigcup_{k=1}^rE_{\{n+k\}}\right|=\sum_{s=0}^r(-1)^s\binom{r}{s}\binom{n+r-s}{m+r}.$$

In particular, when $m=1$ and $r=3$, we have the identity \begin{align}n&=\binom{3}{0}\binom{n+3}{4}-\binom{3}{1}\binom{n+2}{4}+\binom{3}{2}\binom{n+1}{4}-\binom{3}{3}\binom{n}{4}\\&=\binom{n+3}{4}-3\binom{n+2}{4}+3\binom{n+1}{4}-\binom{n}{4}.\end{align} This is equivalent to $$\binom{n+3}{4}=n+3\binom{n+2}{4}-3\binom{n+1}{4}+\binom{n}{4}.$$

Answer 6

I think the following is the simplest prove:

Consider polynomial

$$p(n) = \binom {n+3}4-3\binom {n+2}4+3\binom {n+1}4-\binom n4 -n$$

It is of degree at most $4$. So it is enough to prove it is equal to $0$ for at least $5$ different values of $n$, which is easy to check. Therefore $p(n)=0$ for all $n$.