\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 2}{Due February 11, 2012}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  Students seeking higher than 500 level credit must complete all 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines that apply to all homeworks.

\begin{enumerate}

\item{}[CM 1.2.\{16,15\}] Prove the first three identities below by counting a set in two ways.  In each case, give a single direct argument without manipulating the formulas.  In part (d), find a closed form solution for the sum and give a combinatorial proof.
\begin{multicols}{2}
\begin{enumerate}
	\item $\displaystyle \binom{2n}{n} = 2\binom{2n-1}{n-1}$
	\item $\displaystyle \sum_k \binom{k}{l}\binom{n}{k} = \binom{n}{l}2^{n-l}$
	\item $\displaystyle \sum_{i=1}^n i(n-i) = \sum_{i=1}^n \binom{i}{2}$
	\item $\displaystyle \sum_{j=1}^m (m-j)2^{j-1}$
\end{enumerate}
\end{multicols}

\item{}[CM 1.2.19] Evaluate the following sums using known identities.
\begin{multicols}{2}
\begin{enumerate}
	\item $\displaystyle \sum_{k\ge 0} \frac{1}{k+1}\binom{n}{k}$
	\item $\displaystyle \sum_{k=0}^n (-1)^k\binom{n}{k}\frac{1}{n+1-k}$
\end{enumerate}
\end{multicols}

\item{}[CM 1.2.20] Give a combinatorial proof for the following identity by devising a set that both sides count.
\[ \sum_{k\ge 1} k\binom{m+1}{r+k+1} = \sum_{i=1}^m i2^{i-1}\binom{m-i}{r} \]

\item{}[CM 1.2.28] Evaluate the sums below.  (Hint: Express each sum as a product.)
\begin{multicols}{2}
\begin{enumerate}
	\item $\displaystyle \sum_{S\subseteq [n]} \prod_{i\in S} \frac{1}{i}$
	\item $\displaystyle \sum_{S\subseteq [n]} (-1)^{|S|} \prod_{i\in S} \frac{1}{i}$
\end{enumerate}
\end{multicols}

\item{}[CM 1.2.30] For the identity below,
\begin{enumerate}
	\item Give a combinatorial proof by constructing a set that both sides count.
	\item Use the Binomial Theorem to prove that both sides arise as the coefficient of $x^n$ in the expansion of $(1+3x+x^2)^n$.  Hint: if you are having trouble generating the LHS with the Binomial Theorem, try to apply your combinatorial argument from (a) in the algebraic context.  What plays the role of $j$ in the combinatorial argument?  What is the corresponding mechanism in the algebraic context?
\[ \sum_{j\ge 0} \binom{n}{j}\binom{2j}{j} = \sum_{k\ge 0} \binom{n}{2k}\binom{2k}{k} 3^{n-2k} \]
\end{enumerate}

\item{}[CM 1.2.39] Let $A = \{a_1,\ldots,a_n\}\subset \mathbb{R}$, with $a_1 < \cdots < a_r$.  For $i\in [n]$, let $S_i$ be the family of $i$-element subsets of $A$, and let $\sigma_i = \sum_{B\in S_i} \max(B)$.  For $k\in [n]$, prove that
\[ a_k = \sum_{r=1}^n (-1)^{k+r}\binom{r-1}{k-1}\sigma_r .\]

\end{enumerate}
\end{document}
