Sunday, February 5, 2017

combinatorics - Proof for a certain binomial identity



Let $1\leq m\leq n$ be positive integers. I will appreciate any help proving the following identity

$$
\sum_{k=n}^{n+m}(-1)^k\binom{k-1}{n-1}\binom{n}{k-m}=0
$$

Thanks!


Answer



Here we have Chu-Vandermonde's Identity in disguise.




We obtain for $1\leq m\leq n$
\begin{align*}

\color{blue}{\sum_{k=n}^{n+m}}&\color{blue}{(-1)^k\binom{k-1}{n-1}\binom{n}{k-m}}\\
&=\sum_{k=0}^m(-1)^{k+n}\binom{n+k-1}{n-1}\binom{n}{k+n-m}\tag{1}\\
&=\sum_{k=0}^m(-1)^{k+n}\binom{n+k-1}{k}\binom{n}{m-k}\tag{2}\\
&=(-1)^n\sum_{k=0}^m\binom{-n}{k}\binom{n}{m-k}\tag{3}\\
&=(-1)^n\binom{0}{m}\tag{4}\\
&\,\,\color{blue}{=0}
\end{align*}




Comment:





  • In (1) we shift the index to start with $k=0$.


  • In (2) we apply the binomial identity $\binom{p}{q}=\binom{p}{p-q}$ twice.


  • In (3) we apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.


  • In (4) we finally apply the Chu-Vandermonde identity.



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...