Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 2 / e

The stated identity $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ has an even right side because $n$ is even. Its left side is an odd integer $k$ times the integer binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. An odd multiplier preserves integer parity, so that coefficient must be even. Equivalently, reducing the identity in modular arithmetic gives

Write $n=2r$ and $k=2s$. Partition an $n$-element set into $r$ distinguished pairs, and let $\tau$ interchange the two elements of every pair. It induces an involution on the $k$-element subsets. Every nonfixed subset is paired with its distinct image, so nonfixed subsets contribute an even number to the binomial coefficient $\left(\genfrac{}{}{0ex}{}{2r}{2s}\right)$.

A fixed subset contains either both or neither of the elements of each distinguished pair. Since it contains $2s$ elements, it consists of exactly $s$ whole pairs. There are $\left(\genfrac{}{}{0ex}{}{r}{s}\right)$ such fixed subsets. Counting modulo $2$ therefore givesThe same involution explains part (i): a fixed subset cannot have odd size.