<s>[INST] Showing that two combinatorial expressions are equal Is there an algebraic way of showing that $$\sum_{m=\lceil p / b\rceil}^{c} \left(-1\right)^m \frac{\binom{b\cdot m}{p}}{\binom{b\cdot c}{p}} \sum_{k=m}^{c}k\cdot(-1)^{k} \binom{c}{k} \binom{k}{m} = c\cdot\left[1 - \frac{\binom{b\cdot[c - 1]}{p}}{\binom{b\cdot c}{p}}\right], $$
for all positive integers $b$, $c$, $p$?
Background:
A friend sent me a puzzle, which I've solved in two different ways, and I'd like to convince myself that they're algebraically the same.
Specifically, I was asked to consider the following problem: Suppose we have 80 balls in a bowl of 8 different colours, with 10 of each colour. If we draw 15 of them without replacement, how many colours would we expect to see?
Method 1:
We can find the expected number of colours as the weighted average of the possible number of colours, with the weights being the probabilities: $\bar{k} = \sum_{k} k \cdot P_k$. To do this we need to calculate the probabilities of seeing exactly $k$ colours for all possible values of $k$.
The probability of using just one colour is 0, as $15 > 10$.
The probability of using exactly two colours is $\binom{8}{2} \cdot \frac{\binom{20}{15}}{\binom{80}{15}}$. 
The probability of using exactly at most three colours is  $\binom{8}{3} \cdot \frac{\binom{30}{15}}{\binom{80}{15}}$.This probability however includes some cases where we've picked only two colours. To get the probability of picking exactly three colours, we need to subtract these cases, giving: $\binom{8}{3} \cdot \left[\frac{\binom{30}{15}}{\binom{80}{15}} - \binom{3}{2}\frac{\binom{20}{15}}{\binom{80}{15}}\right]$. Using the inclusion-exclusion principle, the general probability of getting exactly $k$ colours is
$$ 
  P_k = (-1)^{k} \frac{\binom{8}{k}}{\binom{80}{15}} \sum_{m=2}^{k}\left(-1\right)^m \binom{k}{m}\binom{10m}{15}
$$
The expected number of colours can then be written as
$$ \begin{align}
    \bar{k}  &= \sum_{k=2}^8k\cdot(-1)^{k} \frac{\binom{8}{k}}{\binom{80}{15}} \sum_{m=2}^{k}\left(-1\right)^m \binom{k}{m}\binom{10m}{15}\\
    &= \sum_{m=2}^{8} \left(-1\right)^m \frac{\binom{10m}{15}}{\binom{80}{15}} \sum_{k=m}^8k\cdot(-1)^{k} \binom{8}{k} \binom{k}{m}.
\end{align}  $$
Method 2
Alternatively, I reasoned that for any given colour, the probability of having that colour in the draw is $P_{\mathrm{c}} = 1 - \frac{\binom{70}{15}}{\binom{80}{15}}$. If the colour is included, it contributes 1 to the total number of colours, and if not, it contributes 0. The expected value of the number of colours is then
$$
    \bar{k} = \sum_{\mathrm{colours}} P_{\mathrm{c}} = 8 - 8 \frac{\binom{70}{15}}{\binom{80}{15}}
$$
I can calculate both of these numbers, and for this particular case, they are the same. 
What I'd like is to understand why they should be equal in general -- there's nothing in the derivations which limits us to 8 colours, 10 balls of each colour and 15 picks.
It's been a while since I had any combinatorics, so I'm a bit stuck
 [/INST] We seek to show that
$$\sum_{m=\lceil p/b \rceil}^c (-1)^m {bm\choose p}
\sum_{k=m}^c (-1)^k k {c\choose k} {k\choose m}
= c{bc\choose p} - c{b(c-1)\choose p}.$$
We have
$${c\choose k} {k\choose m}
= \frac{c!}{(c-k)! \times m! \times (k-m)!}
= {c\choose m} {c-m\choose c-k}$$
and we get for the LHS
$$\sum_{m=\lceil p/b \rceil}^c (-1)^m {bm\choose p}
{c\choose m}
\sum_{k=m}^c (-1)^k k {c-m\choose c-k}
\\ = \sum_{m=\lceil p/b \rceil}^c (-1)^m {bm\choose p}
{c\choose m}
\sum_{k=0}^{c-m} (-1)^{k+m} (k+m) {c-m\choose c-m-k}
\\ = \sum_{m=\lceil p/b \rceil}^c {bm\choose p}
{c\choose m}
\sum_{k=0}^{c-m} (-1)^{k} (k+m) {c-m\choose k}.$$
Now we have
$$m \sum_{k=0}^{c-m} (-1)^{k} {c-m\choose k}
= m [[ c = m ]]$$
so that this becomes
$$ c {bc\choose p} +
\sum_{m=\lceil p/b \rceil}^c {bm\choose p}
{c\choose m}
\sum_{k=0}^{c-m} (-1)^{k} k {c-m\choose k}
\\ = c {bc\choose p} +
\sum_{m=\lceil p/b \rceil}^c {bm\choose p}
(c-m) {c\choose m}
\sum_{k=1}^{c-m} (-1)^{k} {c-m-1\choose k-1}
\\ = c {bc\choose p} -
\sum_{m=\lceil p/b \rceil}^c {bm\choose p}
(c-m) {c\choose m}
\sum_{k=0}^{c-m-1} (-1)^{k} {c-m-1\choose k}.$$
Again we have
$$\sum_{k=0}^{c-m-1} (-1)^{k} {c-m-1\choose k}
= [[c-1 = m]]$$
so we find
$$c {bc\choose p} -
{b(c-1)\choose p} (c-(c-1)) {c\choose c-1}
= c {bc\choose p} - c {b(c-1)\choose p}.$$
This is the claim.
</s>