Is there an algebraic way of showing that $$sum_m=lceil p / brceil^c left(-1right)^m fracbinombcdot mpbinombcdot cp sum_k=m^ckcdot(-1)^k binomck binomkm = ccdotleft[1 - fracbinombcdot[c - 1]pbinombcdot cpright], $$

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: $bark = 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 $binom82 cdot fracbinom2015binom8015$.

The probability of using exactly at most three colours is $binom83 cdot fracbinom3015binom8015$.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: $binom83 cdot left[fracbinom3015binom8015 - binom32fracbinom2015binom8015right]$. Using the inclusion-exclusion principle, the general probability of getting exactly $k$ colours is

$$
P_k = (-1)^k fracbinom8kbinom8015 sum_m=2^kleft(-1right)^m binomkmbinom10m15
$$

The expected number of colours can then be written as

$$ beginalign
bark &= sum_k=2^8kcdot(-1)^k fracbinom8kbinom8015 sum_m=2^kleft(-1right)^m binomkmbinom10m15\
&= sum_m=2^8 left(-1right)^m fracbinom10m15binom8015 sum_k=m^8kcdot(-1)^k binom8k binomkm.
endalign $$

Method 2

Alternatively, I reasoned that for any given colour, the probability of having that colour in the draw is $P_mathrmc = 1 - fracbinom7015binom8015$. 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

$$
bark = sum_mathrmcolours P_mathrmc = 8 - 8 fracbinom7015binom8015
$$

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

We seek to show that

$$sum_m=lceil p/b rceil^c (-1)^m bmchoose p
sum_k=m^c (-1)^k k cchoose k kchoose m
= cbcchoose p - cb(c-1)choose p.$$

We have

$$cchoose k kchoose m
= fracc!(c-k)! times m! times (k-m)!
= cchoose m c-mchoose c-k$$

and we get for the LHS

$$sum_m=lceil p/b rceil^c (-1)^m bmchoose p
cchoose m
sum_k=m^c (-1)^k k c-mchoose c-k
\ = sum_m=lceil p/b rceil^c (-1)^m bmchoose p
cchoose m
sum_k=0^c-m (-1)^k+m (k+m) c-mchoose c-m-k
\ = sum_m=lceil p/b rceil^c bmchoose p
cchoose m
sum_k=0^c-m (-1)^k (k+m) c-mchoose k.$$

Now we have

$$m sum_k=0^c-m (-1)^k c-mchoose k
= m [[ c = m ]]$$

so that this becomes

$$ c bcchoose p +
sum_m=lceil p/b rceil^c bmchoose p
cchoose m
sum_k=0^c-m (-1)^k k c-mchoose k
\ = c bcchoose p +
sum_m=lceil p/b rceil^c bmchoose p
(c-m) cchoose m
sum_k=1^c-m (-1)^k c-m-1choose k-1
\ = c bcchoose p -
sum_m=lceil p/b rceil^c bmchoose p
(c-m) cchoose m
sum_k=0^c-m-1 (-1)^k c-m-1choose k.$$

Again we have

$$sum_k=0^c-m-1 (-1)^k c-m-1choose k
= [[c-1 = m]]$$

so we find

$$c bcchoose p -
b(c-1)choose p (c-(c-1)) cchoose c-1
= c bcchoose p - c b(c-1)choose p.$$

This is the claim.