3
$\begingroup$

I came a cross a kind of combinatorial expression in my research. I'm wondering if there is a way to simplify or rewrite it. The expression is pretty simple. So I'm posting it here instead of MO. It is the following.

$\displaystyle \sum\limits_{i=0}^n (-1)^i{n \choose i} {x-i \choose l}, $

where in my case $x,l$ are some positive integers. It's not hard to show when $l< n$, the expression is $0$. But I would like to know about any possible formula for $l\geq n$. I tried to search in some combinatorial identity book. There are a lot of similar expressions, but none of the identities seems to apply. Any idea or answers will be greatly appreciated.

$\endgroup$
0
3
$\begingroup$

First let $x=m$ and $l=n+j$ & use $\binom{m-i}{n+j} =[y^{n+j}]: (1+y)^{m-i}$ \begin{eqnarray*} S= \sum_{i=0}^{n} (-1)^i \binom{n}{i} \binom {m-i}{n+j} = [y^{n+j}]: \sum_{i=0}^{n} (-1)^i \binom{n}{i} (1+y)^{m-i} \\ = [y^{n+j}]: (1+y)^m (1- \frac{1}{1+y})^n \\ =[y^{n+j}]: (1+y)^{m-n} y^n =\binom{m-n}{j}. \end{eqnarray*}

$\endgroup$
1
  • $\begingroup$ Wow! I didn't expect it's that easy. Thank you so much! $\endgroup$ – Honglu Sep 10 '17 at 17:14
3
$\begingroup$

$$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}\binom{x-k}{l} &=\sum_{k=0}^n(-1)^k\binom{n}{n-k}\sum_{j=0}^{n-k}\binom{x-n}{l-j}\binom{n-k}{j}\tag{1}\\ &=\sum_{j=0}^n\sum_{k=0}^{n-j}(-1)^k\binom{n}{n-j}\binom{x-n}{l-j}\binom{n-j}{k}\tag{2}\\ &=\sum_{j=0}^n\binom{n}{n-j}\binom{x-n}{l-j}[j=n]\tag{3}\\ &=\binom{x-n}{l-n}\tag{4} \end{align} $$ Explanation:
$(1)$: Vandermonde's Identity
$(2)$: change order of summation and $\binom{n}{n-k}\binom{n-k}{j}=\binom{n}{n-j}\binom{n-j}{k}$
$(3)$: $\sum\limits_{k=0}^{n-j}(-1)^k\binom{n-j}{k}=[j=n]$
$(4)$: apply the Iverson Brackets

$\endgroup$
2
$\begingroup$

Just to show another way to solve it.

The backward Delta (finite difference) is defined as $$ \eqalign{ & \nabla _{\,x} \,f(x) = f(x) - f(x - 1) \cr & \nabla _{\,x} ^n \,f(x) = \nabla _{\,x} \,\left( {\nabla _{\,x} ^{n - 1} \,f(x)} \right) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^k \left( \matrix{ n \cr k \cr} \right)\;f(x - k)} \cr} $$

So $$ \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^k \left( \matrix{ n \cr k \cr} \right)\;\left( \matrix{ x - k \cr l \cr} \right)} = \nabla _{\,x} ^n \,\left( \matrix{ x \cr l \cr} \right) = \nabla _{\,x} ^n \,{{x^{\,\underline {\,l\,} } } \over {l!}} = {1 \over {l!}}\nabla _{\,x} ^n \,x^{\,\underline {\,l\,} } $$ where $x^{\,\underline {\,l\,}} $ is the Falling Factorial

It is easy to demonstrate that $$ \eqalign{ & \nabla _{\,x} \;x^{\,\underline {\,l\,} } = x^{\,\underline {\,l\,} } - \left( {x - 1} \right)^{\,\underline {\,l\,} } = l\left( {x - 1} \right)^{\,\underline {\,l - 1\,} } \cr & \nabla _{\,x} ^n \,x^{\,\underline {\,l\,} } = l^{\,\underline {\,n\,} } \left( {x - n} \right)^{\,\underline {\,l - n\,} } \cr} $$ and therefore $$ \eqalign{ & \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^k \left( \matrix{ n \cr k \cr} \right)\;\left( \matrix{ x - k \cr l \cr} \right)} = \nabla _{\,x} ^n \,\left( \matrix{ x \cr l \cr} \right) = {1 \over {l!}}\nabla _{\,x} ^n \,x^{\,\underline {\,l\,} } = \cr & = {1 \over {l!}}l^{\,\underline {\,n\,} } \left( {x - n} \right)^{\,\underline {\,l - n\,} } = {1 \over {\left( {l - n} \right)!}}\left( {x - n} \right)^{\,\underline {\,l - n\,} } = \left( \matrix{ x - n \cr l - n \cr} \right) \cr} $$

which is valid for $x$ integer, but also real or even complex.

By the way, it might be interesting to note that the Binomial Inversion also assures you that the reverse of the above is true, i.e. $$ \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^k \left( \matrix{ n \cr k \cr} \right)\;\left( \matrix{ x - k \cr l \cr} \right)} = \left( \matrix{ x - n \cr l - n \cr} \right)\quad \Leftrightarrow \quad \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^k \left( \matrix{ n \cr k \cr} \right)\;\left( \matrix{ x - k \cr l - k \cr} \right)} = \left( \matrix{ x - n \cr l \cr} \right) $$

$\endgroup$
2
  • $\begingroup$ Interesting technique, using difference operators and falling factorials. I must admit, I did not think the answer would be that simple, so I am grateful for your independent verification. $\endgroup$ – Donald Splutterwit Sep 10 '17 at 18:02
  • 1
    $\begingroup$ @DonaldSplutterwit: Glad to have presented another approach. And yes, in situations like this, finite difference might be very helpful and straight. $\endgroup$ – G Cab Sep 10 '17 at 18:43

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.