Simplifying a binomial coefficient summation I am trying to solve a problem related to expected value, but I am having problem trying to reduce a binomial coefficient expression.
How can I prove the following?
Assume $a \le k \le n$,
$$\sum_{i=0}^{k}\frac{{ i \cdot  {{k}\choose{i}}}\cdot {{n-k}\choose{a-i}}} {{{n}\choose{a}}} 
 = \frac{a\cdot k}{n}$$
 A: Here is an algebraic method. We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. In this way we can write
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}\tag{1}
\end{align*}

We obtain
\begin{align*}
\color{blue}{\sum_{i=0}^k}\color{blue}{i\binom{k}{i}\binom{n-k}{a-i}}
&=k\sum_{i=1}^k\binom{k-1}{i-1}\binom{n-k}{a-i}\tag{2}\\
&=k\sum_{i=0}^{k-1}\binom{k-1}{i}\binom{n-k}{a-1-i}\tag{3}\\
&=k\sum_{i=0}^{k-1}\binom{k-1}{i}[z^{a-1-i}](1+z)^{n-k}\tag{4}\\
&=k[z^{a-1}](1+z)^{n-k}\sum_{i=0}^{k-1}\binom{k-1}{i}z^i\tag{5}\\
&=k[z^{a-1}](1+z)^{n-1}\tag{6}\\
&\,\,\color{blue}{=k\binom{n-1}{a-1}}\tag{7}
\end{align*}
and the claim follows.

Comment:

*

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


*In (3) we shift the index to start with $k=0$.


*In (4) we apply (1).


*In (5) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$ and use the linearity of the coefficient of operator.


*In (6) we apply the binomial theorem.


*In (7) we select the coefficient of $[z^{a-1}]$.
A: \begin{align}
\sum_{i=0}^{k}\frac{{ i \binom{k}{i}} {{n-k}\choose{a-i}}} {\binom{n}{a}} 
&= \sum_{i=1}^{k}\frac{{ i \binom{k}{i}} {{n-k}\choose{a-i}}} {\binom{n}{a}} \\
&= \frac{\sum_{i=1}^{k}{ i \binom{k}{i}} {{n-k}\choose{a-i}}} {\binom{n}{a}} \\ 
&= \frac{\sum_{i=1}^{k}{ i  \frac{k}{i} \binom{k-1}{i-1}} {{n-k}\choose{a-i}}} {\frac{n}{a}\binom{n-1}{a-1}} \\ 
&= \frac{ak}{n}\cdot \frac{\sum_{i=1}^{k}{\binom{k-1}{i-1}} {{n-k}\choose{a-i}}} {\binom{n-1}{a-1}} \\ 
&= \frac{ak}{n} &&\text{by Vandermonde's identity}
\end{align}
A: We can do double counting.
Suppose you wish to select a committee of $a$ people out of $k$ adults and $n-k$ kids. You also need to choose one of the adults in the committee to be the leader. We can do this by selecting a number of adults, say $i$ out of the available $k$ adults, and select one out of these $i$ adult committee member to be the leader. Then we need to fill the committee by selecting $a-i$ out of the available $n-k$ kids. The number of way to do this is given by the following:
$$
\sum_{i=0}^{k}i\cdot\binom{k}{i}\cdot\binom{n-k}{a-i}
$$
Another way to form the committee is to first select one leader out of $k$ adults, and then select $a-1$ members out of combined $n-1$ remaining adults and kids. The number of way to do this is given below.
$$
k\cdot\binom{n-1}{a-1}
$$
Because both expressions are used to count the same thing, they must be equal.
$$
\sum_{i=0}^{k}i\cdot\binom{k}{i}\cdot\binom{n-k}{a-i}
=
k\cdot\binom{n-1}{a-1}
$$
Now simply divide both side by $\binom{n}{a}$ to get your initial expression
A: This is the expected value of the hypergeometric distribution.

