Combinatorial Interpretation

First, recall $\left(\begin{array}{c}n\\ k\end{array}\right)$ is the number of possible $k$ things chosen from an $n$ things.

Then if we have a set of $n$ eggs that includes exactly one bad egg, there are $\left(\begin{array}{c}n\\ k\end{array}\right)$ ways to choose $k$ eggs out of $n$ eggs.

Now, when we choose $k$ eggs, consider the set as “including no rotten eggs” or “including a rotten egg”. Then the selections can be considered as below：

• $\left(\begin{array}{c}n-1\\ k\end{array}\right)$：the number of selections involve no rotten egg but only $k$ good eggs
• $\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$：the number of selections involve one rotten egg and $k-1$ good eggs

Adding two numbers together gives the formula.

　Proof　：

$$\begin{array}{rcl}\left(\begin{array}{c}n-1\\ k-1\end{array}\right)+\left(\begin{array}{c}n-1\\ k\end{array}\right)& =& \frac{(n-1)!}{(k-1)!\{(n-1)-(k-1)\}!}+\frac{(n-1)!}{k!(n-1-k)!}\\ & & \\ & =& \frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-1-k)!}\\ & & \\ & =& \frac{(n-1)!}{(k-1)!(n-k)!}\times \frac{k}{k}+\frac{(n-1)!}{k!(n-1-k)!}\times \frac{n-k}{n-k}\\ & & \\ & =& \frac{k(n-1)!}{k!(n-k)!}+\frac{(n-k)(n-1)!}{k!(n-k)!}\\ & & \\ & =& \frac{(n-1)!\{k+(n-k)\}}{k!(n-k)!}\\ & & \\ & =& \frac{(n-1)!\times n}{k!(n-k)!}\\ & & \\ & =& \frac{n!}{k!(n-k)!}\\ & & \\ & =& \left(\begin{array}{c}n\\ k\end{array}\right)\end{array}$$