Prove that $\sum_{i=0}^{k}\binom{k-i}{b}\binom{i}{a-1}=\binom{k+1}{a+b}$ I am trying to prove this identity from an exercise:
Given $k$, $a$, $b$, prove that
$$
\sum_{i=0}^{k}\binom{k-i}{b}\binom{i}{a-1}=\binom{k+1}{a+b}
$$
However, I'm having trouble using existing identities to prove this. Any help would be much appreciated.
 A: Start from
$$\sum_{q=a-1}^{k-b} {k-q\choose b} {q\choose a-1}
= \sum_{q=0}^{k+1-b-a} {k+1-a-q\choose b} {q+a-1\choose a-1}
\\ = \sum_{q=0}^{k+1-a-b}
{k+1-a-q\choose k+1-a-b-q} {q+a-1\choose a-1}
\\ = [z^{k+1-a-b}] (1+z)^{k+1-a} \sum_{q=0}^{k+1-a-b}
{q+a-1\choose a-1} \frac{z^q}{(1+z)^q}.$$
The coefficient extractor enforces the range and we get
$$[z^{k+1-a-b}] (1+z)^{k+1-a} \sum_{q\ge 0}
{q+a-1\choose a-1} \frac{z^q}{(1+z)^q}
\\ = [z^{k+1-a-b}] (1+z)^{k+1-a}
\frac{1}{(1-z/(1+z))^a}
\\ = [z^{k+1-a-b}] (1+z)^{k+1-a}
\frac{(1+z)^a}{(1+z-z)^a}
\\ = [z^{k+1-a-b}] (1+z)^{k+1}
= {k+1\choose k+1-a-b} = {k+1\choose a+b}.$$
This  is  the  claim. BTW  when  $k-q\lt  b$  or  $k-b\lt q$  we  have
$(k-q)^\underline{b} = 0.$ (This zero value does not include $q=k$ and
$b=0$ because we required $k-q\lt b$.)  Similarly when $0\le q\lt a-1$
we have  $q^\underline{a-1} =  0.$ (This zero  value does  not include
$q=0$ and  $a=1$ because  we required $q\lt  a-1$.)  Applies  to $k,b$
non-negative integers  and $a$ a  positive integer. For the  sum range
not to be empty we also need $k-b\ge a-1$ or $k+1\ge a+b.$ 
A: 
We obtain
  \begin{align*}
\color{blue}{\sum_{i=0}^k\binom{k-i}{b}\binom{i}{a-1}}
&=\sum_{i=0}^k\binom{k-i}{k-i-b}\binom{i}{i-a+1}\tag{1}\\
&=\sum_{i=0}^k\binom{-b-1}{k-i-b}\binom{-a}{i-a+1}(-1)^{k-i-b+i-a+1}\tag{2}\\
&=\binom{-a-b-1}{-a-b+k+1}(-1)^{-a-b+k+1}\tag{3}\\
&\,\,\color{blue}{=\binom{k+1}{a+b}}\tag{4}\\
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$ twice.

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

*In (3) we apply  Chu-Vandermonde's identity.

*In (4) we use  again the identities $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ and $\binom{p}{q}=\binom{p}{p-q}$.
A: Consider there are $k+1$ distinct objects. The number of ways ways to choose a subset of $a+b$ objects is $\dbinom{k+1}{a+b}$.
Now consider that the $k+1$ objects are the numbers in $S=\{0, 1, 2,\ldots, k\}$. Then sort the resultant subset and index the numbers using $T=\{1,2,\ldots, a-1, a, a+1,\ldots,a+b\}$, so that in the subset if number $x$ is indexed before number $y$ using indices $T$, then $x$ is also smaller than $y$.
i.e. order-preserving, injective functions from $T$ to $S$.
(And yes, $T$ is $1$-based for my convenience)
Let $f:T\to S$ be one such function from the subset index of $T$ to the number in $S$.
Consider $f(a) = i$, i.e. among the $k+1$ numbers we have chosen $i\in S$ as the $a$th number in the subset. Then


*

*Among the $i$ numbers $\{0, 1, 2, \ldots, i-1\}$, we have to choose $a-1$ of them for $f(1), f(2), \ldots, f(a-1)$ to map to, i.e. choose $a-1$ numbers to add into the subset.

*Independently, among the $k-i$ numbers $\{i+1, i+2, \ldots, k\}$, we have to choose $b$ of them for $f(a+1), f(a+2), \ldots, f(a+b)$ to map to, i.e. choose $b$ numbers to add into the subset.


Summing over all choices of $i$, this proves that
$$\sum_{i=0}^k\binom{k-i}{b}\binom{i}{a-1} = \binom{k+1}{a+b}$$
