PlanetMath: ${n\choose r}$ is an integer

(more info)

Math for the people, by the people.

Main Menu

${n\choose r}$ is an integer

(Theorem)

Theorem 1 For $n\ge r \ge 0$ , the binomial coefficient

$\displaystyle {n \choose r}$

is an integer.

Proof. The proof is by induction on

. For

, the claim is clear. Thus, suppose the claim holds for $n\ge 1$ . For $r=1,\ldots, n$ , Pascal's rule gives

$\displaystyle {n +1 \choose r} = {n\choose r} + {n\choose r-1}.$

That is, ${n +1 \choose 1}, \ldots, {n+1 \choose n}$ are integers. Since

$\displaystyle {n +1\choose 0} = 1, \quad {n +1\choose n+1} = 1$

the proof is complete. $\qedsymbol$

Anyone with an account can edit this entry. Please help improve it!

" ${n\choose r}$ is an integer" is owned by matte.

(view preamble)

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: complete, Pascal's rule, clear, induction, integer, binomial coefficient
There is 1 reference to this entry.

This is version 3 of ${n\choose r}$ is an integer, born on 2005-02-14, modified 2005-02-14.
Object id is 6744, canonical name is NchooseRIsAnInteger.
Accessed 4600 times total.

Classification:

AMS MSC:	05A10 (Combinatorics :: Enumerative combinatorics :: Factorials, binomial coefficients, combinatorial functions)
	11B65 (Number theory :: Sequences and sets :: Binomial coefficients; factorials; $q$-identities)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact