Numbers and Sets | Part IA, 2006

Define the binomial coefficient (nr)\left(\begin{array}{l}n \\ r\end{array}\right) and prove that

(n+1r)=(nr)+(nr1) for 0<rn\left(\begin{array}{c} n+1 \\ r \end{array}\right)=\left(\begin{array}{c} n \\ r \end{array}\right)+\left(\begin{array}{c} n \\ r-1 \end{array}\right) \quad \text { for } 0<r \leqslant n

Show also that if pp is prime then (pr)\left(\begin{array}{l}p \\ r\end{array}\right) is divisible by pp for 0<r<p0<r<p.

Deduce that if 0k<p0 \leqslant k<p and 0rk0 \leqslant r \leqslant k then

(p+kr)(kr)(modp).\left(\begin{array}{c} p+k \\ r \end{array}\right) \equiv\left(\begin{array}{c} k \\ r \end{array}\right) \quad(\bmod p) .

Typos? Please submit corrections to this page on GitHub.