Prove that $\sum_{i=0}^{k}\binom{k-i}{b}\binom{i}{a-1}=\binom{k+1}{a+b}$

Question

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.

Answer 1

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.$

Answer 2

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}$.

Answer 3

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}$$