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

[5.1.5] Let $c \leq b \leq 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})$ .
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.
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.)
[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.
1. In how many different ways can we form the smaller group with a junior liaison?
2. 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?
3. Use parts (a) and (b) to give a simple expression for $\sum_{k = 0}^{n} k {(\binom{n}{k})}^{2}$ .
[5.1.16] Using algebra, find and prove an identity of the form $\sum_{k = 0}^{n} \frac{(2 n)!}{k!^{2} (n - k)!^{2}} = {(\binom{?}{n})}^{2}$ . (Hint: in the terms on the LHS, multiply the numerator and denominator by $n!^{2}$ .)
[5.1.30] Recall that $k! \geq {(\frac{k}{e})}^{k}$ . Use this to prove that for $1 \leq k \leq n$ , we have ${(\frac{n}{k})}^{k} \leq (\binom{n}{k}) \leq {(\frac{𝑛𝑒}{k})}^{k}$ .