(a) Let $S$ be the set of all functions $f: \mathbb{N} \rightarrow \mathbb{R}$. Define $\delta: S \rightarrow S$ by

$$(\delta f)(n)=f(n+1)-f(n)$$

(i) Define the binomial coefficient $\left(\begin{array}{l}n \\ r\end{array}\right)$ for $0 \leqslant r \leqslant n$. Setting $\left(\begin{array}{l}n \\ r\end{array}\right)=0$ when $r>n$, prove from your definition that if $f_{r}(n)=\left(\begin{array}{l}n \\ r\end{array}\right)$ then $\delta f_{r}=f_{r-1}$.

(ii) Show that if $f \in S$ is integer-valued and $\delta^{k+1} f=0$, then

$$f(n)=c_{0}\left(\begin{array}{l} n \\ k \end{array}\right)+c_{1}\left(\begin{array}{c} n \\ k-1 \end{array}\right)+\cdots+c_{k-1}\left(\begin{array}{l} n \\ 1 \end{array}\right)+c_{k}$$

for some integers $c_{0}, \ldots, c_{k}$.

(b) State the binomial theorem. Show that

$$\sum_{r=0}^{n}(-1)^{r}\left(\begin{array}{l} n \\ r \end{array}\right)^{2}=\left\{\begin{array}{cl} 0 & \text { if } n \text { is odd } \\ (-1)^{n / 2}\left(\begin{array}{c} n \\ n / 2 \end{array}\right) & \text { if } n \text { is even } \end{array}\right.$$