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{eqnarray*}\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{eqnarray*}