2
$\begingroup$

I'm having trouble proving the negative binomial identity ${r\choose k} = (-1)^k{k-r-1\choose k}$. Here's what I've got so far:

I know that ${k-r-1\choose k} = {(k-r-1)!\over k!(-r-1)!}$, and the numerator when expanded out has k terms. If we distribute the $(-1)^k$ across each of those terms we end up with the numerator $(r-k+1)(r-k+2)\cdots(r-1)(r)$, which is exactly the numerator that we want for $r\choose k$. However, the denominator for $r\choose k$ is $k!(r-k)!$ rather than $k!(-r-1)!$ What am I missing here?

$\endgroup$
  • $\begingroup$ Have you tried using the sum identity: ${r+1\choose k+1}={r\choose k+1}+{r\choose k}$? $\endgroup$ – abiessu Oct 11 '13 at 0:40
  • $\begingroup$ No but it isn't apparent to me why I should be using that identity in this problem. $\endgroup$ – Kvass Oct 11 '13 at 0:43
  • $\begingroup$ I think the identity is different for negatives, my apologies. I was trying to make it work in an inductive way... $\endgroup$ – abiessu Oct 11 '13 at 1:09
  • $\begingroup$ Use Gamma function reflection property. $\endgroup$ – Felix Marin Oct 11 '13 at 4:09
  • 1
    $\begingroup$ @abiessu That will be a chance for the OP to learn it. See my answer below. $\endgroup$ – Felix Marin Oct 11 '13 at 21:26
1
$\begingroup$

Hint:

Writing out the terms,

$${r \choose k}={(r-k+1)(r-k+2)\cdots(r-1)r\over 1\cdot 2\cdot 3\cdots k}$$

What terms of "r choose k" are not present due to being canceled out? Note that the count continues from $(r-1)\cdot r\cdots$ instead of from the other side...

$\endgroup$
  • $\begingroup$ Oh I got it - I think I must have been double counting the denominator -> once I've expanded out $r...(r-k+1)$, all that's left on the denominator in either expression is just $k!$. $\endgroup$ – Kvass Oct 11 '13 at 3:35
0
$\begingroup$

$\displaystyle{\Gamma\left(z\right)\mbox{: Gamma function}.\qquad\qquad} $Euler Reflection Formula: $\displaystyle{\quad% \Gamma\left(z\right)\,\Gamma\left(1 - z\right) = {\pi \over \sin\left(\pi z\right)} }$

\begin{align} {r \choose k} &= {r! \over k!\left(r - k\right)!} = {1 \over k!}\,{\Gamma\left(r + 1\right) \over \Gamma\left(r - k + 1\right)} \tag{1} \end{align}

\begin{align} {\Gamma\left(r + 1\right) \over \Gamma\left(r - k + 1\right)} &= \overbrace{% {\pi \over \sin\left(\pi\left[r + 1\right]\right) \Gamma\left(1 - \left[1 + r\right]\right)}} ^{\displaystyle{\Gamma\left(r\ + 1\right)}}\quad \overbrace{% {\sin\left(\pi\left[r - k + 1\right]\right) \Gamma\left(1 - \left[r - k + 1\right]\right) \over \pi}} ^{\displaystyle{1 \over \Gamma\left(r\ - k\ + 1\right)}} \\[3mm]&= {1 \over -\sin\left(\pi r\right)\Gamma\left(-r\right)} \left\{\vphantom{\Large A}% -\sin\left(\pi\left[r - k\right]\right)\Gamma\left(k - r\right)\right\} = {\sin\left(\pi\left[r - k\right]\right) \over \sin\left(\pi r\right)}\, {\left(k - r - 1\right)! \over \left(-r - 1\right)!} \end{align}

By replacing this result in $\left(1\right)$, we get \begin{equation} {r \choose k} = {\sin\left(\pi\left[r - k\right]\right) \over \sin\left(\pi r\right)}\, {\left(k - r - 1\right)! \over k!\left(-r - 1\right)!} \quad\Longrightarrow\quad {r \choose k} = {\sin\left(\pi\left[r - k\right]\right) \over \sin\left(\pi r\right)}\, {k - r - 1 \choose k} \tag{2} \end{equation}

When $k$ is an integer, $\displaystyle{% {\sin\left(\pi\left[r - k\right]\right) \over \sin\left(\pi r\right)}\, } = \left(-1\right)^{k}$. Then, $\left(2\right)$ becomes

For $r, k \in {\mathbb Z};\quad r \leq -1$: $$\color{#ff0000}{\large% {r \choose k} \color{#000000}{\ =\ } \left(-1\right)^{k}{k - r - 1 \choose k}\,, \qquad \color{#000000}{k \geq 0\,,\quad r \leq -1}} \tag{3} $$ When $k \leq r \leq -1$, we use formula $\left(3\right)$ as follows: $$ \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{r \choose k} = {r \choose r - k} = \left(-1\right)^{r - k} {\left[r - k\right] - r - 1 \choose r - k} = \left(-1\right)^{r - k}{-k - 1 \choose r - k}\,, \qquad k \leq r \leq -1 \tag{4} $$ Otherwise, $\displaystyle{{r \choose k} = 0}$ since $\Gamma\left(z\right)$ has poles at $z = 0, -1, -2, \ldots$.

A detailed account of this topic is given in http://mathworld.wolfram.com/BinomialCoefficient.html

$\endgroup$
  • $\begingroup$ Apart from the fact that this comforts me in my belief that introducing the Gamma function to handle binomial coefficient invariably results in a horrible mess (but this I admit is very much a matter of taste), I cannot help but observe that when $r\geq k\geq0$ are integers (probably the main intended application of this identity) the expression $\frac{(k-r-1)!}{(-r-1)!}$ is not defined (it gives the indeterminate form $\frac\infty\infty$ at best). If on the other hand $r<0$ is an integer as you say in the final part, the initial $\frac{r!}{(r-k)!}$ has similar problems. $\endgroup$ – Marc van Leeuwen Oct 12 '13 at 16:27
  • $\begingroup$ @MarcvanLeeuwen Indeed, they are limiting cases. For the sake of simplicity it is manipulated in that way. We can set all calculations for complex values and take limits when complex values go to negative integers and all the calculations yield the correct result. Just for 'practical purposes' we perform the derivation in the way explained above but it is implicit that there is some limit procedure involved in. The first time I saw this kind of extension to complex values I had the same feeling. However , it was clear that the 'correct' way' involves the 'limit' mentioned above. Thanks. $\endgroup$ – Felix Marin Oct 12 '13 at 21:15

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.