4
$\begingroup$

Let $a$, $b$, $c$ and $n$ be non-negative integers.

By counting the number of committees consisting of $n$ sentient beings that can be chosen from a pool of $a$ kittens, $b$ crocodiles and $c$ emus in two different ways, prove the identity

$$\sum\limits_{\substack{i,j,k \ge 0; \\ i+j+k = n}} {{a \choose i}\cdot{b \choose j}\cdot{c \choose k} = {a+b+c \choose n}}$$

where the sum is over all non-negative integers $i$, $j$ and $k$ such that $i+j+k=n.$

I know that this is some kind of combinatorial proof. My biggest problem is that I've never really done a proof.

3 Answers 3