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.

  • 1
    $\begingroup$ 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$? $\endgroup$ – Brian M. Scott Oct 7 '16 at 10:36

I will assume that the lefthand side is supposed to be


It’s somewhat helpful to let $\ell=k+5$, so that $k=\ell-5$ and rewrite this as


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$.

  • $\begingroup$ thank you! well explained :D $\endgroup$ – Tom.A Oct 7 '16 at 10:51
  • $\begingroup$ @Tom: You’re welcome! $\endgroup$ – Brian M. Scott Oct 7 '16 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.