\problemdata
{binary string}
{counting}
{f01 ps9}
\begin{problem} Let $\set{\mathtt{0},\mathtt{1}}^n$ be the set on length-$n$
binary strings, where $n>1$.  Let $A_i$ be the set of length-$n$ strings
that have a \texttt{1} in their $i^{th}$ position.

\begin{problemparts}

\problempart What is the cardinal of the intersection of $k$ of the sets
$A_1,A_2,\dots$?

\solution{$2^{n-k}$, namely, the number of length-$n$ strings that have
a \texttt{1} in $k$ designated positions.}

\problempart Using the inclusion-exclusion principle, prove that 
\begin{equation}\label{iesum}
\sum_{k=1}^{n} \frac{(-1)^{k+1}\binom{n}{k}}{2^k} = 1 - \frac{1}{2^n}
\end{equation}

\solution{
The inclusion-exclusion principle gives:
\begin{eqnarray*}
2^n - 1 &=& \card{\lgunion_{j=1}^{n} A_{i}}\\
	&=& \sum_{\emptyset \neq S \subseteq \set{1,\dots,n}} (-1)^{\card{S}+1}
				\card{\bigcap_{i \in S} A_{i}} \\
        &=& \sum_{\emptyset \neq S \subseteq \set{1,\dots,n}} (-1)^{\card{S}+1} 2^{n-\card{S}}\\
	&=& \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} \frac{2^n}{2^k},\\
\end{eqnarray*}
and now equation~(\ref{iesum}) follows by dividing the expressions above
by $2^n$.}

\end{problemparts}
\end{problems}

