\problemdata                                                             
        {Binomial Coefficients} % latex-friendly label for the prob.
        {finding sums, algebraic/combinatorial arguments} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Final, 7} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}  
\begin{problemparts}         
\problempart
Give a closed-form formula for $\sum_{i=0}^{n} {n \choose i}$. Justify your answer

\solution{
\[\sum_{i=0}^{n} {n \choose i} = 2^n \]
}
\problempart What is
$${{n\choose 0}} - {{n\choose 1}} + {{n \choose 2}} - {{n \choose 3}} \ldots$$
Justify your answer
\solution{
Recall that 
$$(a+b)^n = \sum_{i=0}^n {{n \choose i}} a^i b^{n-i}$$

Now let $a=-1$ and $b=1$. Clearly $(a+b)^n=0$ for all $n>0$, so
$$0 = \sum_{i=0}^n {{n \choose i}} (-1)^i$$

Since ${n \choose i} = 0$ for all $i > n$, we can let the sum go to
infinity:
$$0 = \sum_{i=0}^\infty {{n \choose i}} (-1)^i$$

Finally, note that $(-1)^i$ alternates between $+1$ and $-1$, so this
sum expands to:

$$0 ={{n \choose 0}}  - {{n\choose 1}} + {{n \choose 2}} - {{n \choose 3}} \ldots$$
}

\ppart Prove algebraically that $\binom{2n}{n}$ is even.
\hint It may be helpful to draw Pascal's triangle in order to get some
intuition about why this must be true. However, your proof should make
no reference to Pascal's triangle whatsoever.

\solution{
\[
\binom{2n}{n}=\binom{2n-1}{n-1}+\binom{2n-1}{n}=2\binom{2n-1}{n}
\]
}


\problempart Prove that $\binom{2n}{n}$ is even using a
combinatorial argument.

\solution{
Suppose that you're looking for the number of bit strings of length $2n$ which have exactly $n$ 1's. There are $\binom{2n}{n}$ such strings. Now, look at one of these strings. It has $n$ 1's, so it also has $n$ 0's at the remaining positions. Somewhere else in our collection there exists exactly one string whose 1's are precisely at those positions occupied by the 0's in our first string. We can consider these two to be a \emph{pair}. It is easy to see that no string in our collection could possibly be ``single". Since all of our $\binom{2n}{n}$ occur in pairs, this number must be even.
} 

\end{problemparts}
\end{problem}
                                 