\problemdata      
        {?} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {?} % Source (if known)
        {F01, TU9} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem}
By now you have probably seen the identity
\begin{equation}\label{binminus}
\sum_{i=0}^n (-1)^i \binom{n}{i} = 0
\end{equation}
more than once.
\bparts

\ppart This identity is an immediate consequence of the Binomial Theorem.
Explain how.

\solution{We know the
\begin{equation}\tag{Binomial Theorem}
(x + y)^n = \sum_{i=0}^n \binom{n}{i}x^iy^{n-i}.
\end{equation}
So let $x = -1$ and $y=1$ to obtain equation~(\ref{binminus}).
}

\ppart Conclude from equation~(\ref{binminus}) that $\set{1,2,\dots, n}$ has
an equal number of odd- and even-size subsets.

\solution{The number of odd-size subsets is the number of subsets of size $1, 3,
\dots, 2i+1, \dots$ namely
\[
\binom{n}{1} + \binom{n}{3} + \cdots + \binom{n}{2i+1} + \cdots
\]
which we can write as
\begin{equation}\label{oddterms}
\sum_{i=1}^{\ceil{n/2}} \binom{n}{2i-1}.
\end{equation}
But this is exactly the absolute value of the sum of the negative-valued
terms on the LHS of equation~(\ref{binminus}).

Likewise, the number of even-size subsets is the number of subsets of size
$0, 2, \dots, 2i, \dots$ namely
\[
\binom{n}{0} + \binom{n}{2} + \cdots + \binom{n}{2i} + \cdots
\]
which we can write as
\begin{equation}\label{eventerms}
\sum_{i=0}^{\floor{n/2}} \binom{n}{2i}.
\end{equation}
But this is exactly the sum of the nonnegative-valued terms on the LHS of
equation~(\ref{binminus}).

So the LHS of equation~(\ref{binminus}) also equals
expression~(\ref{eventerms}) minus expression~(\ref{oddterms}).  Hence,
the values of the expressions~(\ref{oddterms}) and~(\ref{eventerms}) are
the same.}

\ppart Conversely, equation~(\ref{binminus}) will follow if we show that
there is an equal number of even- and odd-size subsets of
$\set{1,2,\dots,n}$ whenever $n>0$.  Prove that there are an equal number
by defining a simple bijection between the even-size and odd-size subsets
of $\set{1,2,\dots,n}$.

\solution{
An elegant bijection is 
\[
g(S) \eqdef \begin{cases}
            S-\set{n} & \text{if } n \in S\\
            S \union \set{n} & \text{otherwise}.
            \end{cases}
\]

Another approach is based on the fact that if $n$ is odd, then a subset
has odd size iff its complement is even size, and vice-versa.  So if $n$
is odd, the letting any subset $S \subseteq \set{1,2,\dots,n}$ map to its
complement $\bar{S} \eqdef \set{1,2,\dots,n} - S$ is a bijection between
the even- and odd-sized subsets.

To extend this idea to the case when $n$ is even, we observe that $n-1$ is
odd, so we use the bijection, $f$, we have from the even-size subsets of
$\set{1,2,\dots,n-1}$ to the odd-sized ones.  We can extend this bijection
to the remaining even-size subsets of $\set{1,2,\dots,n}$, namely the ones
that contain $n$.  To do this, map $S \union \set{n}$, where $S$ is an
even-size subset of $\set{1,2,\dots,n-1}$, to the set $f(S) \union
\set{n}$.}


\end{problemparts}
\end{problem}