% COUNTING ARGUMENT
\begin{problem}[10]
Use a combinatorial argument to prove the following identity. In other
words, argue that both sides of the equality are different ways of
counting the same thing. (Note: We do not want an algebraic proof.)
\[
\binom{n}{k} = \binom{n-2}{k} + 2 \binom{n-2}{k-1} + \binom{n-2}{k-2}
\]

\solution[\vspace*{5cm}]{

The number of ways to choose a k-subset from a $n$ set is
$\binom{n}{k}$.  Let $a,b$ be two different elements from the
$n$ set.  Then the number of k-subsets from the $n$ set can be
found as follows:
\begin{enumerate}
\item Don't choose $a$ or $b$ and choose all k elements from the rest.
This gives $\binom{n-2}{k}$ choices.
\item Choose $a$, not $b$, and $k-1$ elements from the rest.  This
gives $\binom{n-2}{k-1}$ choices.
\item Choose $b$, not $a$, aand $k-1$ elements from the rest.  This
gives also $\binom{n-2}{k-1}$ choices.
\item Choose $a,b$ and $k-2$ elements from the rest.  This gives
$\binom{n-2}{k-2}$ choices.
\end{enumerate}
So we can also choose our k-subsets in $\binom{n-2}{k} + 2
\binom{n-2}{k-1} + \binom{n-2}{k-2}$ ways.}
\end{problem}

\comment{Eric}{Solution fixed. I agree the grading would be a bit judgemental, 
but I think it is certainly a good problem to see if students know how to 
present a combinatorial argument in a professional manner.}

\comment{Radhika}{Its not bad but may be hard to grade. I am a littlew
worried that people might either see it or not; which can be
demoralizing}

\iffalse
\comment{Radhika}{Alternative problem.
Suppose we had $m_r$ red balls, $m_b$ blue balls,
and $m_y$ yellow balls. 

(a) Consider the following combinatorial equality

$\dbinom{n}{m_r,m_b,m_y}
= \dbinom{n}{m_r} \dbinom{n-m_r}{m_b} \dbinom{n-m_r-m_b}{m_b}$

The LHS represents the number of different sequnces in which we can
line up these balls, because that is the number of permutations of the
balls with each color of nball repreated the corresponding number of
times.

Prove this equality by arguing that the RHS is another way of counting
the same thing.

(b) Suppose that we put all of the balls in an urn, and I take out
balls one at a time. What's the probability of getting the seuqnce
$m_r, m_b, m_y$ red blue and yellow balls?

Solution: All sequences are equally likely. 1/total possible sequences
from above.
}

\fi