1

I was playing around with the concept of subtraction of binomial expresions such as $\binom{n+k}{2}-\binom{n}{2}$, $\binom{n+k}{3}-\binom{n}{3}$, etc...

I was wondering if there was a known general formula for the expression $\binom{n+k}{m}-\binom{n}{m}$, with $n>k>m$. Ideally, I'm looking for general formulas which only make use of binomial coefficients.

I've figured out the first couple of terms, but I can't seem to find the general formula:

$\binom{n+k}{2}-\binom{n}{2}=\binom{k}{2}+\binom{k}{1}\binom{n}{1}$

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

$\binom{n+k}{4}-\binom{n}{4}=\binom{k}{4}+\binom{k}{3}\binom{n}{1}+\binom{k}{1}\binom{n}{3}+\binom{k}{2}\binom{n}{2}-\frac{11}{24}\binom{k}{1}\binom{n}{1}$*

*I am not completely sure that the math behind this one is totally correct. It does seem to break an otherwise natural trend.

Thanks in advance for your help!

Chappers
  • 67,606
Pablo López
  • 13

1 Answers1

1

Note that $$ {n+j \choose m} - {n+j-1 \choose m} = {n+j-1 \choose m-1} $$ so that $$ \eqalign{{n + k \choose m} - {n \choose m} &= \sum_{j=1}^k \left({n+j \choose m} - {n+j-1 \choose m} \right)\cr &= \sum_{j=1}^k {n+j-1 \choose m-1}} $$

Hmm: what you have found seems to be something different:

$$ {n+k \choose m} = \sum_{j=0}^m {k \choose m-j} {n \choose j} $$

See Vandermonde's identity

Robert Israel
  • 448,999
  • Thank you! It seems like the Vandermonde identity is exactly what I'm looking for. Not only that, but it also explains part of the behaviour of the formula which I wasn't seing before. It seems like I have to check my last equation, which must be wrong. For now I think you've answered the question. – Pablo López May 12 '17 at 23:17