Paper 4, Section II, E

Numbers and Sets | Part IA, 2021

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

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

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

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

f(n)=c0(nk)+c1(nk1)++ck1(n1)+ckf(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 c0,,ckc_{0}, \ldots, c_{k}.

(b) State the binomial theorem. Show that

r=0n(1)r(nr)2={0 if n is odd (1)n/2(nn/2) if n is even \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.

Typos? Please submit corrections to this page on GitHub.