<s>[INST] Simplification of Combinatorial Expression I have been solving a problem and have been stuck on it for hours now.
I can't recall any combinatorial approach/formula for the below expression :
$$\sum_{i=a+1}^n {i-1 \choose a}{n-i \choose k-a}$$
Any sort of help would be appreciated. I know it is a norm to share my approach as well to show that I have put an effort but honestly I don't have any clue on this particular question.
Thanks!
 [/INST] What follows is admittedly not the simplest proof. We post here by way
of enrichment and to showcase four techniques, coefficient extractors,
the Iverson bracket, residues and the Leibniz rule. 
We seek to show that
$$\sum_{q=a+1}^n {q-1\choose a} {n-q\choose k-a}
= {n\choose k+1}$$
where $k\ge a$ for the binomial coefficient to be defined,
and $n\ge a+1$ or alternatively
$$\sum_{q=0}^{n-a-1} {q+a\choose a} {n-a-1-q\choose k-a}
= {n\choose k+1}.$$
The LHS is
$$[z^{k-a}] (1+z)^{n-a-1}
\sum_{q\ge 0} {q+a\choose a} (1+z)^{-q} [[q\le n-a-1]]
\\ = [z^{k-a}] (1+z)^{n-a-1}
\sum_{q\ge 0} {q+a\choose a} (1+z)^{-q}
[w^{n-a-1}] \frac{w^q}{1-w}
\\ = [z^{k-a}] (1+z)^{n-a-1} [w^{n-a-1}] \frac{1}{1-w}
\sum_{q\ge 0} {q+a\choose a} (1+z)^{-q} w^q
\\ = [z^{k-a}] (1+z)^{n-a-1} [w^{n-a-1}] \frac{1}{1-w}
\frac{1}{(1-w/(1+z))^{a+1}}
\\ = [z^{k-a}] (1+z)^{n} [w^{n-a-1}] \frac{1}{1-w}
\frac{1}{(1+z-w)^{a+1}}.$$
This is
$$[z^{k-a}] (1+z)^n (-1)^a
\mathrm{Res}_{w=0} \frac{1}{w^{n-a}}
\frac{1}{w-1} \frac{1}{(w-(1+z))^{a+1}}.$$
Now the residue at infinity for $w$ is zero by inspection, residues
sum to zero and the residue at $w=1$ yields
$$[z^{k-a}] (1+z)^n (-1)^a \frac{1}{(-1)^{a+1} z^{a+1}}
= - {n\choose k+1}.$$
This is the claim if we can show that the contribution from the pole at
$w=1+z$ is zero. We get (Leibniz rule)
$$\frac{1}{a!} \left(\frac{1}{w^{n-a}} \frac{1}{w-1}\right)^{(a)}
= \frac{1}{a!}
\sum_{q=0}^a {a\choose q}
\frac{(-1)^q (n-1-a+q)!}{(n-1-a)! \times w^{n-a+q}}
\frac{(-1)^{a-q} (a-q)!}{(w-1)^{a+1-q}}
\\ = (-1)^a \sum_{q=0}^a {n-1-a+q\choose q}
\frac{1}{w^{n-a+q}} \frac{1}{(w-1)^{a+1-q}}.$$
We thus obtain for the contribution
$$[z^{k-a}] (1+z)^n  \sum_{q=0}^a {n-1-a+q\choose q}
\frac{1}{(1+z)^{n-a+q}} \frac{1}{z^{a+1-q}}
\\ =   \sum_{q=0}^a {n-1-a+q\choose q}
[z^{k+1-q}] (1+z)^{a-q} = 0$$
because $a\ge q$ and $k+1\gt a.$ This concludes the argument.
</s>