$\left(\genfrac{}{}{0pt}{}{n}{r}\right)$ is an integer

Theorem 1.

For $n\mathrm{\ge }r\mathrm{\ge }\mathrm{0}$, the binomial coefficient

$$\left(\genfrac{}{}{0pt}{}{n}{r}\right)$$

is an integer.

Proof.

The proof is by induction on $n$. For $n=0$, theclaim is clear. Thus, suppose the claim holds for $n\ge 1$.For $r=1,\mathrm{\dots },n$, Pascal’s rule gives

$$\left(\genfrac{}{}{0pt}{}{n+1}{r}\right)=\left(\genfrac{}{}{0pt}{}{n}{r}\right)+\left(\genfrac{}{}{0pt}{}{n}{r-1}\right).$$

That is, $\left(\genfrac{}{}{0pt}{}{n+1}{1}\right),\mathrm{\dots },\left(\genfrac{}{}{0pt}{}{n+1}{n}\right)$ areintegers.Since

$$\left(\genfrac{}{}{0pt}{}{n+1}{0}\right)=1,\left(\genfrac{}{}{0pt}{}{n+1}{n+1}\right)=1$$

the proof is complete.∎