Paper 4, Section I, 2E2 \mathrm{E}

Numbers and Sets | Part IA, 2014

Define the binomial coefficients (nk)\left(\begin{array}{l}n \\ k\end{array}\right), for integers n,kn, k satisfying nk0n \geqslant k \geqslant 0. Prove directly from your definition that if n>k0n>k \geqslant 0 then

(nk)+(nk+1)=(n+1k+1)\left(\begin{array}{l} n \\ k \end{array}\right)+\left(\begin{array}{c} n \\ k+1 \end{array}\right)=\left(\begin{array}{c} n+1 \\ k+1 \end{array}\right)

and that for every m0m \geqslant 0 and n0n \geqslant 0,

k=0m(n+kk)=(n+m+1m)\sum_{k=0}^{m}\left(\begin{array}{c} n+k \\ k \end{array}\right)=\left(\begin{array}{c} n+m+1 \\ m \end{array}\right)

Typos? Please submit corrections to this page on GitHub.