% COUNTING ARGUMENT
\begin{problem}
Prove the following equality with a combinatorial argument. In other
words, argue that both sides of the equality are different ways of
counting the same thing.

$$\binom{n}{k} = \binom{n-2}{k} + 2 \binom{n-2}{k-1} + \binom{n-2}{k-2}$$

\solution[\vspace*{5cm}]{
FIX SOLUTION: changed LHS from $\binom{n+2}{k}$ to $\binom{n}{k}$.


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

\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. We also discussed an alternative based ion inclass
problem 8W, 4(b), which I am outlining below, but I think maybe we
should pursue it only if we have enough time. }

\comment{Radhika}{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 seuqnces are equally likely. 1/total possible seuqnces
from above
}

