0
$\begingroup$

I am trying to prove $\sum_{j=1}^{n-k}{n \choose j}{n-k-1 \choose j-1}={2n-k-1 \choose n-k}$. I tried to apply Vandermonde's Identity, however I have not been able to.

$\endgroup$
1
  • $\begingroup$ This has been asked on this site before, but I don’t know how to keyword search for it since it’s a formula $\endgroup$ Jun 5, 2020 at 18:22

1 Answer 1

2
$\begingroup$

If you rewrite the left-hand side as $$\sum_{j=1}^{n-k}\binom{n}{j} \binom{n-k-1}{n-k-j},$$ you can then use Vandermonde's identity.

$\endgroup$
3
  • 1
    $\begingroup$ The key to knowing how to rewrite the left side is to remember two things: Firstly, that the symmetric identity exists ($\binom{n}{k} = \binom{n}{n-k}$), and secondly, that the idea behind Vandermonde's identity is summing up cases after splitting into two groups. Thus, the bottom numbers of the binomial coefficients should add up to a constant. Your indices are both increasing in your original problem, but by applying the symmetric identity to one of them, it is now decreasing, and they can now add to a constant. $\endgroup$
    – zhuli
    Jun 5, 2020 at 18:17
  • $\begingroup$ But to apply Vandermonde's identity shouldn't it be $\sum_{j=0}^{n-k}$? $\endgroup$
    – DFL
    Jun 6, 2020 at 12:48
  • 2
    $\begingroup$ @DanielLinnenbrink The case $j=0$ involves a term $\binom{n-k-1}{n-k}$ which is zero by definition. $\endgroup$
    – angryavian
    Jun 6, 2020 at 16:50

You must log in to answer this question.

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