1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Notice that the formula for $\binom{n}{r}$ is $\frac{n!}{r!(n-r)!}$ $\endgroup$ – Franklin Pezzuti Dyer May 12 '17 at 19:26
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Plopez May 12 '17 at 23:17

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.