# Combinatorial proof of $\sum_{k=0}^n\binom{k+5}5\binom{n-k+3}3=\binom{n+9}9$

I have been given an identity to prove in two ways (using generating functions and using a combinatorial explanation that fits both sides of the equation). $$\sum_{k=0}^n\binom{k+5}5\binom{n-k+3}3=\binom{n+9}9$$ Solving it with generating functions seemed OK, noticing that both sides are generated by $$f(x)=\frac1{(1-x)^{10}}$$ A combinatorial suggestion will be very appreciated if possible.

• The statement as written is false: for $n=1$ it says that $\binom65\binom43+\binom65\binom33$, which is $30$, is equal to $\binom{10}9$, which is $10$. Is $\binom{n+5}5$ supposed to be $\binom{k+5}5$? – Brian M. Scott Oct 7 '16 at 10:36

$$\sum_{k=0}^n\binom{k+5}5\binom{n-k+3}3\;.$$
It’s somewhat helpful to let $\ell=k+5$, so that $k=\ell-5$ and rewrite this as
$$\sum_{\ell=5}^{n+5}\binom{\ell}5\binom{n+8-\ell}3\;.$$
HINT: The righthand side is clearly the number of $9$-element subsets of the set $\{0,1,\ldots,n+8\}$. Classify these sets by their sixth smallest element. For a given $\ell$, how many $9$-element subsets of $\{0,1,\ldots,n+8\}$ have $\ell$ as sixth smallest element? Note that this means that the set must have $5$ elements smaller than $\ell$ and $3$ elements larger than $k$. Note also that because I started the set at $0$, it has $\ell$ elements smaller than $\ell$.