1
$\begingroup$

I am reading Riordan's Combinatorial Identities. On page 8 there is a formula like screenshot. I have no problem to understand the first three lines, in which we use $(-1)^m \cdot \binom{-n}{m} = \binom{n + m - 1 }{m}$ twice and Vandemonde identity in between. I could not understand the last step.

riordan_page8

$\endgroup$

2 Answers 2

1
$\begingroup$

Note: It is helpful to use indices with lower and upper limit to clarify aspects of this kind.

We obtain \begin{align*} \color{blue}{\binom{n-p}{m}}&=(-1)^m\binom{p-n+m-1}{m}\tag{1}\\ &=(-1)^m\sum_{k=0}^m\binom{p}{m-k}\binom{-n+m-1}{k}\tag{2}\\ &=\sum_{k=0}^m\binom{p}{m-k}\binom{n-m+k}{k}(-1)^{m+k}\tag{3}\\ &\color{blue}{=\sum_{k=0}^m\binom{p}{k}\binom{n-k}{m-k}(-1)^k}\tag{4} \end{align*} and the claim follows according to your analysis and as indicated in the comment below.

Comment:

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

  • In (2) we apply Vandermonde's Identity*.

  • In (3) we use again the binomial identity from (1).

  • In (4) we shift the index $k\to m-k$.

$\endgroup$
1
$\begingroup$

I was stuck for a while then I realize I can just replace $m-k$ with $u$ and last step comes naturally from the previous step:

$$ \binom{p}{u} \cdot \binom{n-u}{m-u} $$

The power of $-1$ becomes $(-1)^{u+2k} = (-1)^u$. Eventually rename $u$ with dummy variable $k$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .