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

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math378}{Homework 12}{Due Fri. Apr 17, 2026}

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

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}
\item {} [5.1.5] Let $c\le b\le a$ be non-negative integers.  Give two proofs, one algebraic and the other combinatorial, for $\binom{a}{b}\binom{b}{c} = \binom{a}{c}\binom{a-c}{b-c}$.

\item Recall that Pascal's identity for binomial coefficients is $\binom{n}{k}=\binom{n-1}{k-1} + \binom{n-1}{k}$ and tells the story that all $k$-element subsets of a set of size $n$ either include or omit the last element.  

Suppose $a,b,c$ are non-negative integers summing to $n$.  What equation tells the story that in a partition of $[n]$ into $3$ labeled parts of sizes $a$, $b$, and $c$, the last element $n$ belongs to one of the three parts?  Explain.

\item {} Give a combinatorial proof of the identity $\sum_{t=k}^n \binom{t}{k} = \binom{n+1}{k+1}$.  (Hint: let $A$ be the set of all $(k+1)$-element subsets of $[n+1]$.  Group the sets in $A$ by their maximum element.  Look at, for example, $n=5$ and $k=2$ for insight into the general case.)

\item {} [5.1.22] We have a group of math majors consisting of $n$ sophomores and $n$ juniors.  We want to form a smaller group that has a total of $n$ students in it, but from among that group we want to designate one of the students to serve as a departmental liaison.  The liaison needs to be a junior, but there is no other restriction on the students chosen for the smaller group.
\begin{enumerate}
	\item In how many different ways can we form the smaller group with a junior liaison?
	\item Let $k$ be a positive integer.  In how many ways can we pick $k$ juniors, a liaison from among the $k$ juniors, and $n-k$ sophomores?
	\item Use parts (a) and (b) to give a simple expression for $\sum_{k=0}^n k\binom{n}{k}^2$.
\end{enumerate}

\item {} [5.1.16] Using algebra, find and prove an identity of the form $\sum_{k=0}^n \frac{(2n)!}{k!^2(n-k)!^2} = \binom{?}{n}^2$.  (Hint: in the terms on the LHS, multiply the numerator and denominator by $n!^2$.)

\item {} [5.1.30] Recall that $k! \ge \left(\frac{k}{e}\right)^k$.  Use this to prove that for $1\le k\le n$, we have $\left(\frac{n}{k}\right)^k \le \binom{n}{k} \le \left(\frac{ne}{k}\right)^k$.


\end{enumerate}
\end{document}
