Combinatorial proof of ${{n}\choose{4}}={{n-3}\choose{4}}+3{{n-3}\choose{3}}+3{{n-3}\choose{2}}+n-3$

Question

I need help solving this problem ${{n}\choose{4}}={{n-3}\choose{4}}+3{{n-3}\choose{3}}+3{{n-3}\choose{2}}+n-3$. I was thinking for the LHS that I'm choosing 4 students to get a prize out of n students but I am not sure about the RHS. Please help.

Answer 1

Split $n$ into two groups, $A$ and $B$, $|A| = n-3$ and $|B|=3$. This could correspond, for example, to some additional attribute of the $B$ group.

Then focus on the split of choices between the subgroups:

• choosing all from $A$ leads to $\dbinom{n-3}{4}$ options.
• choosing $3$ from $A$, $1$ from $B$ leads to $\dbinom{n-3}{3}\dbinom 31 = 3\dbinom{n-3}{3}$ options.
• choosing $2$ from $A$, $2$ from $B$ leads to $\dbinom{n-3}{2}\dbinom 32 = 3\dbinom{n-3}{2}$ options.
• choosing $1$ from $A$, $3$ from $B$ leads to $\dbinom{n-3}{1}\dbinom 33 = 1\dbinom{n-3}{1} = n-3$ options.

These cover all the possibilities from a simple choice of $4$ from the original $n$ so sum to the same value.

Answer 2

Use Vandermonde identity: $$ \binom{n}{4}=\sum_{i\ge 0} \binom{n-3}{4-i}\binom{3}{i}, $$ which has the well-known combinatorial interpretation: if you have to choose $4$ objects on a total of $n$ objects, then it is the same of choosing $i$ in the first $3$ ones, and $4-i$ in the remaining ones, summing over $i\ge 0$.

Answer 3

Simply use Pascal's relation repeatedly: $$\binom n4=\binom{n-1}{4}+\binom{n-1}3=\biggl[\binom{n-2}{4}+\binom{n-2}3\biggr]+\biggl[\binom{n-2}{3}+\binom{n-2}2\biggr]=\dotsm$$