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

$$\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 $p$ is prime then $\left(\begin{array}{l}p \\ r\end{array}\right)$ is divisible by $p$ for $0<r<p$.

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

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