Binomial Coefficients and the Binomial Theorem: From Pascal's Triangle to the Multinomial Theorem

We prove Pascal's identity, the binomial theorem, the Vandermonde convolution, and the multinomial theorem. We then extend the discussion to generalized (negative) binomial coefficients and Lucas' theorem.

Folio Official

March 1, 2026

1 Pascal's Identity

Theorem 1 (Pascal's identity).

For

1 \leq r \leq n - 1

(r n) = (r - 1 n - 1) + (r n - 1) .

Proof.

Consider choosing an

r

-element subset of a set

S

with

∣ S ∣ = n

. Fix a particular element

x \in S

. Every

r

-element subset either contains

x

or it does not. If

x

is included, the remaining

r - 1

elements must be chosen from the other

n - 1

elements, giving

(r - 1 n - 1)

subsets. If

x

is excluded, all

r

elements must come from the remaining

n - 1

, giving

(r n - 1)

subsets. The result follows by the addition principle. □

Remark 2.

Repeated application of Pascal's identity produces the well-known triangular array called Pascal's triangle. Its

n

-th row (

n = 0, 1, 2, \dots

) contains

(0 n), (1 n), \dots, (n n)

2 The Binomial Theorem

Theorem 3 (Binomial theorem).

For any

x, y

and any nonnegative integer

n

(x + y)^{n} = r = 0 \sum n (r n) x^{r} y^{n - r} .

Proof.

We proceed by induction on

n

. When

n = 0

, both sides equal

1

. Suppose the identity holds for

n - 1

, where

n \geq 1

. Then

(x + y)^{n} = (x + y) (x + y)^{n - 1} = (x + y) r = 0 \sum n - 1 (r n - 1) x^{r} y^{n - 1 - r}

= r = 0 \sum n - 1 (r n - 1) x^{r + 1} y^{n - 1 - r} + r = 0 \sum n - 1 (r n - 1) x^{r} y^{n - r} .

Substituting

s = r + 1

and collecting terms, the coefficient of

x^{s} y^{n - s}

becomes

(s - 1 n - 1) + (s n - 1)

, which equals

(s n)

by Pascal's identity. Checking the boundary terms completes the proof. □

3 The Vandermonde Convolution

Theorem 4 (Vandermonde convolution).

(r m + n) = k = 0 \sum r (k m) (r - k n)

Proof.

Consider choosing

r

elements from the disjoint union of a set

A

with

∣ A ∣ = m

and a set

B

with

∣ B ∣ = n

. The number of ways to select

k

elements from

A

and

r - k

from

B

(k m) (r - k n)

. Summing over

k

yields

(r m + n)

. □

4 The Multinomial Theorem

Theorem 5 (Multinomial theorem).

(x_{1} + x_{2} + \dots + x_{k})^{n} = n_{1} + n_{2} + \dots + n_{k} = n n_{i} \geq 0 \sum (n _{1} , n _{2} , \dots , n _{k} n) x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{k}^{n_{k}}

where the multinomial coefficient is defined by

(n _{1} , n _{2} , \dots , n _{k} n) = \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}

Proof.

When expanding

(x_{1} + \dots + x_{k})^{n}

, one selects a single

x_{i}

from each of the

n

factors. The number of ways to choose

x_{1}

exactly

n_{1}

times,

x_{2}

exactly

n_{2}

times, and so on, equals the multinomial coefficient

\frac{n !}{n _{1} ! \dots n _{k} !}

, which counts the ways to partition

n

positions into

k

groups of the prescribed sizes. □

5 Generalized Binomial Coefficients

Definition 6 (Generalized binomial coefficient).

For

α \in R

and

r \in Z_{\geq 0}

, define

(r α) = \frac{α ( α - 1 ) ( α - 2 ) \dots ( α - r + 1 )}{r !} .

When

α

is a negative integer, we have

(r - n) = (- 1)^{r} (r n + r - 1)

Theorem 7.

(r - n) = (- 1)^{r} (r n + r - 1)

Proof.

(r - n) = \frac{( - n ) ( - n - 1 ) \dots ( - n - r + 1 )}{r !} = \frac{( - 1 ) ^{r} \cdot n ( n + 1 ) \dots ( n + r - 1 )}{r !} = (- 1)^{r} (r n + r - 1) .

□

6 Lucas' Theorem

Theorem 8 (Lucas' theorem).

Let

p

be a prime, and write

n

and

r

in base

p

n = \sum_{i} n_{i} p^{i}

and

r = \sum_{i} r_{i} p^{i}

with

0 \leq n_{i}, r_{i} < p

. Then

(r n) \equiv i \prod (r _{i} n _{i}) (mod p) .

Proof.

F_{p} [x]

, the identity

(1 + x)^{p} = 1 + x^{p}

holds (by the binomial theorem and the fact that

p ∣ (k p)

for

1 \leq k \leq p - 1

). Iterating,

(1 + x)^{p^{i}} = 1 + x^{p^{i}}

for all

i \geq 0

. Therefore

(1 + x)^{n} = i \prod (1 + x)^{n_{i} p^{i}} = i \prod (1 + x^{p^{i}})^{n_{i}} = i \prod r_{i} = 0 \sum n_{i} (r _{i} n _{i}) x^{r_{i} p^{i}} .

Comparing coefficients of

x^{r}

on both sides yields the desired congruence. □

Example 9.

Consider

(3 10) (mod 3)

. We have

10 = (101)_{3}

and

3 = (010)_{3}

, so

(3 10) \equiv (0 1) (1 0) (0 1) = 0 (mod 3)

since

(1 0) = 0

. Indeed,

(3 10) = 120 = 40 \times 3

, confirming

120 \equiv 0 (mod 3)

Combinatorics Discrete Mathematics Textbook Binomial Coefficients Binomial Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Binomial Coefficients and the Binomial Theorem: From Pascal's Triangle to the Multinomial Theorem

Folio Official

March 1, 2026

1 Pascal's Identity

Theorem 1 (Pascal's identity).

For

1 \leq r \leq n - 1

(r n) = (r - 1 n - 1) + (r n - 1) .

Proof.

Consider choosing an

r

-element subset of a set

S

with

∣ S ∣ = n

. Fix a particular element

x \in S

. Every

r

-element subset either contains

x

or it does not. If

x

is included, the remaining

r - 1

elements must be chosen from the other

n - 1

elements, giving

(r - 1 n - 1)

subsets. If

x

is excluded, all

r

elements must come from the remaining

n - 1

, giving

(r n - 1)

subsets. The result follows by the addition principle. □

Remark 2.

Repeated application of Pascal's identity produces the well-known triangular array called Pascal's triangle. Its

n

-th row (

n = 0, 1, 2, \dots

) contains

(0 n), (1 n), \dots, (n n)

2 The Binomial Theorem

Theorem 3 (Binomial theorem).

For any

x, y

and any nonnegative integer

n

(x + y)^{n} = r = 0 \sum n (r n) x^{r} y^{n - r} .

Proof.

We proceed by induction on

n

. When

n = 0

, both sides equal

1

. Suppose the identity holds for

n - 1

, where

n \geq 1

. Then

(x + y)^{n} = (x + y) (x + y)^{n - 1} = (x + y) r = 0 \sum n - 1 (r n - 1) x^{r} y^{n - 1 - r}

= r = 0 \sum n - 1 (r n - 1) x^{r + 1} y^{n - 1 - r} + r = 0 \sum n - 1 (r n - 1) x^{r} y^{n - r} .

Substituting

s = r + 1

and collecting terms, the coefficient of

x^{s} y^{n - s}

becomes

(s - 1 n - 1) + (s n - 1)

, which equals

(s n)

by Pascal's identity. Checking the boundary terms completes the proof. □

3 The Vandermonde Convolution

Theorem 4 (Vandermonde convolution).

(r m + n) = k = 0 \sum r (k m) (r - k n)

Proof.

Consider choosing

r

elements from the disjoint union of a set

A

with

∣ A ∣ = m

and a set

B

with

∣ B ∣ = n

. The number of ways to select

k

elements from

A

and

r - k

from

B

(k m) (r - k n)

. Summing over

k

yields

(r m + n)

. □

4 The Multinomial Theorem

Theorem 5 (Multinomial theorem).

(x_{1} + x_{2} + \dots + x_{k})^{n} = n_{1} + n_{2} + \dots + n_{k} = n n_{i} \geq 0 \sum (n _{1} , n _{2} , \dots , n _{k} n) x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{k}^{n_{k}}

where the multinomial coefficient is defined by

(n _{1} , n _{2} , \dots , n _{k} n) = \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}

Proof.

When expanding

(x_{1} + \dots + x_{k})^{n}

, one selects a single

x_{i}

from each of the

n

factors. The number of ways to choose

x_{1}

exactly

n_{1}

times,

x_{2}

exactly

n_{2}

times, and so on, equals the multinomial coefficient

\frac{n !}{n _{1} ! \dots n _{k} !}

, which counts the ways to partition

n

positions into

k

groups of the prescribed sizes. □

5 Generalized Binomial Coefficients

Definition 6 (Generalized binomial coefficient).

For

α \in R

and

r \in Z_{\geq 0}

, define

(r α) = \frac{α ( α - 1 ) ( α - 2 ) \dots ( α - r + 1 )}{r !} .

When

α

is a negative integer, we have

(r - n) = (- 1)^{r} (r n + r - 1)

Theorem 7.

(r - n) = (- 1)^{r} (r n + r - 1)

Proof.

(r - n) = \frac{( - n ) ( - n - 1 ) \dots ( - n - r + 1 )}{r !} = \frac{( - 1 ) ^{r} \cdot n ( n + 1 ) \dots ( n + r - 1 )}{r !} = (- 1)^{r} (r n + r - 1) .

□

6 Lucas' Theorem

Theorem 8 (Lucas' theorem).

Let

p

be a prime, and write

n

and

r

in base

p

n = \sum_{i} n_{i} p^{i}

and

r = \sum_{i} r_{i} p^{i}

with

0 \leq n_{i}, r_{i} < p

. Then

(r n) \equiv i \prod (r _{i} n _{i}) (mod p) .

Proof.

F_{p} [x]

, the identity

(1 + x)^{p} = 1 + x^{p}

holds (by the binomial theorem and the fact that

p ∣ (k p)

for

1 \leq k \leq p - 1

). Iterating,

(1 + x)^{p^{i}} = 1 + x^{p^{i}}

for all

i \geq 0

. Therefore

(1 + x)^{n} = i \prod (1 + x)^{n_{i} p^{i}} = i \prod (1 + x^{p^{i}})^{n_{i}} = i \prod r_{i} = 0 \sum n_{i} (r _{i} n _{i}) x^{r_{i} p^{i}} .

Comparing coefficients of

x^{r}

on both sides yields the desired congruence. □

Example 9.

Consider

(3 10) (mod 3)

. We have

10 = (101)_{3}

and

3 = (010)_{3}

, so

(3 10) \equiv (0 1) (1 0) (0 1) = 0 (mod 3)

since

(1 0) = 0

. Indeed,

(3 10) = 120 = 40 \times 3

, confirming

120 \equiv 0 (mod 3)

Combinatorics Discrete Mathematics Textbook Binomial Coefficients Binomial Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Binomial Coefficients and the Binomial Theorem: From Pascal's Triangle to the Multinomial Theorem

1 Pascal's Identity

2 The Binomial Theorem

3 The Vandermonde Convolution

4 The Multinomial Theorem

5 Generalized Binomial Coefficients

6 Lucas' Theorem

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Binomial Coefficients and the Binomial Theorem: From Pascal's Triangle to the Multinomial Theorem

1 Pascal's Identity

2 The Binomial Theorem

3 The Vandermonde Convolution

4 The Multinomial Theorem

5 Generalized Binomial Coefficients

6 Lucas' Theorem

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry