Paper 4, Section I, 2E2 E

Numbers and Sets | Part IA, 2007

For integers kk and nn with 0kn0 \leqslant k \leqslant n, define (nk)\left(\begin{array}{l}n \\ k\end{array}\right). Arguing from your definition, show that

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

for all integers kk and nn with 1kn11 \leqslant k \leqslant n-1.

Use induction on kk to prove that

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

for all non-negative integers kk and nn.

Typos? Please submit corrections to this page on GitHub.