\documentclass[10pt]{article} % 
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{psfrag}
\usepackage{amsmath,amssymb}
%\input{preface}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}


\date{Spring 2016}


\begin{document} 
\begin{center}
{\bf Math 432 -- Combinatorics\\
Homework 4}\\
Due  Feb 19, 2016.
\end{center}

Work the following problems. Show all your work. Each problem is 4 points.\\



\begin{enumerate}




\item Use generating function to evaluate the following sum:
\[ \sum_{k=1}^n k{n\choose k}^2. \]


\item  In how many ways can one pick $25$ coins that are pennies, nickels, or dimes,
with at least three nickels, at most five dimes and an even number of pennies?



\item (B2, Putnam 1992) For nonnegative integers $n$ and $k$, define $Q(n,k)$ to be the coefficient of $x^k$ in the expansion of $(1+x+x^2+x^3)^n$. Prove that 
\[
Q(n,k)=\sum_{j=0}^k{n\choose j}{n\choose k-2j}.
\]

\item Prove the identity below. (hint: choose $x$ appropriately in $\sum{2n\choose n}x^n=(1-4x)^{-1/2}$.)
$$\sum (-1)^k {n-k\choose k}{2n-2k\choose n-k}=2^n$$


\item Evaluate the sum below using convolution, and give a combinatorial proof of the resulting identity.
\[ \sum_{j=0}^k {n+k-j-1\choose k-j}{m+j-1\choose j}. \]




\item For positive integers $m,n$, using generating function to prove that $$\sum_{k} {n+k\choose m+2k}{2k\choose k}\frac{(-1)^k}{k+1}={n-1\choose m-1}.$$



\end{enumerate}

\end{document}


