Past exam of the mathematics course of the University of Cambridge / 2021 / ia / Paper 4 / 5E (Numbers and Sets)

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ as the number of $r$-element subsets of an $n$-element set, equivalently as $n!/[r!(n-r)!]$. Partitioning the $r$-element subsets of $\{1,\dots ,n+1\}$ according to whether they contain $n+1$ proves Pascal's identityThus the forward difference operator satisfies

We use induction on $k$. If $k=0$, then $\delta f=0$, so the integer-valued function $f$ is constant. For $k>0$, the integer-valued function $\delta f$ satisfies ${\delta }^k(\delta f)=0$. By induction it is an integer linear combination ofPart (i) shows that replacing each $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ by $\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)$ gives an integer-valued discrete antiderivative. Subtracting the resulting integer linear combination from $f$ leaves a function with zero forward difference, hence an integer constant. This giveswith every $c_j\in \mathbb{Z}$.

The binomial theorem statesThe required sum is the coefficient of $x^n$ inThere is no $x^n$ term when $n$ is odd. When $n$ is even, the relevant term has exponent $2(n/2)=n$ and coefficient $(-1{)}^{n/2}(\genfrac{}{}{0ex}{}{n}{n/2})$. Hence