TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Vandermonde's identity $(\binom{m + n}{k}) = \sum_{i < k + 1} (\binom{m}{i}) (\binom{n}{k - i})$

Statement

For all $m, n, k \in N$ , in $N$ ,

$(\binom{m + n}{k}) = \sum_{i < k + 1} (\binom{m}{i}) (\binom{n}{k - i}),$

the sum running over $i = 0, 1, \dots, k$ and $k - i$ being an ordinary difference throughout that range. No restriction relating $k$ to $m$ and $n$ is needed: the terms with $i > m$ or $k - i > n$ vanish because the corresponding binomial coefficients are $0$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

Facts & Assumptions

Given: Naturals $m$ , $n$ , $k$ ; the disjoint sets $M : = m \times {0}$ and $N : = n \times {1}$ ; and $σ (k) = {0, 1, \dots, k}$ .

[L1]

Binomial coefficients (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ): $∣ [X]^{j} ∣ = (\binom{∣ X ∣}{j})$ for finite $X$ , and $[X]^{j}$ is finite.

[L2]

Cardinality (The cardinality $∣ A ∣$ of a finite set): transport along a bijection; $∣ X ∣ = ∣ Y ∣$ iff $X \approx Y$ for finite $X$ , $Y$ .

[L3]

The sum rule (The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition) and the bridge $\sum_{i \in σ (k)} u_{i} = \sum_{i < σ (k)} u_{i}$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form, Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ ).

[L4]

The product rule $∣ X \times Y ∣ = ∣ X ∣ ∣ Y ∣$ (The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ ).

[L5]

Subsets (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ): a subset of a finite set is finite with cardinality at most that of the set.

[L6]

Maps (Injection, surjection, bijection, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ): a map with a two-sided inverse is a bijection.

[L7]

Arithmetic: if $i + t = k$ then $t = k - i$ , since $\leq$ is defined additively and addition is cancellative; and $j < σ (k) ⟺ j \leq k$ for every $j \in N$ , so $σ (k) = {0, 1, \dots, k}$ (Order on the natural numbers, Addition is cancellative, On $N$ the order is membership: $m < n ⟺ m \in n$ ). The cardinalities $∣ M ∣ = m$ and $∣ N ∣ = n$ are not assumed here; they are computed in step 1.1.

Proof

technique · direct

1.1

A disjoint pair with the right cardinalities. Put $M : = m \times {0}$ and $N : = n \times {1}$ . These are disjoint, since an element of $M$ has second coordinate $0$ and one of $N$ has second coordinate $1$ ; and $x \mapsto (x, 0)$ and $x \mapsto (x, 1)$ are bijections from $m$ and $n$ onto them, so $∣ M ∣ = m$ and $∣ N ∣ = n$ by [L2]. Hence $∣ M \cup N ∣ = m + n$ by [L3], and $∣ [M \cup N]^{k} ∣ = (\binom{m + n}{k})$ by [L1].

L1L2L3L6L7construct

1.2

The partition. For $i < σ (k)$ put $B_{i} : = {S \in [M \cup N]^{k} : ∣ S \cap M ∣ = i}$ . Every $S \in [M \cup N]^{k}$ lies in exactly one $B_{i}$ , because $S \cap M \subseteq S$ gives $∣ S \cap M ∣ \leq k$ by [L5], that is $∣ S \cap M ∣ \in σ (k)$ ; and the $B_{i}$ are pairwise disjoint since $S$ determines $∣ S \cap M ∣$ .

L1L5

2.1

Counting a block. Fix $i < σ (k)$ . The map $S \mapsto (S \cap M, S \cap N)$ sends $B_{i}$ into $[M]^{i} \times [N]^{k - i}$ : for $S \in B_{i}$ the sets $S \cap M$ and $S \cap N$ are disjoint with union $S$ , since $S \subseteq M \cup N$ , so $k = i + ∣ S \cap N ∣$ by [L3] and $∣ S \cap N ∣ = k - i$ by [L7]. The map $(U, V) \mapsto U \cup V$ is a two-sided inverse: $U \subseteq M$ and $V \subseteq N$ are disjoint, so $∣ U \cup V ∣ = i + (k - i) = k$ by [L3], and $(U \cup V) \cap M = U$ , $(U \cup V) \cap N = V$ . Hence $B_{i} \approx [M]^{i} \times [N]^{k - i}$ and $∣ B_{i} ∣ = (\binom{m}{i}) (\binom{n}{k - i})$ by [L1], [L2] and [L4].

step 1.1step 1.2L1L2L3L4L6L7construct

3.1

Adding the blocks. By step 1.2 the family $(B_{i})_{i \in σ (k)}$ is a pairwise disjoint family of finite sets with union $[M \cup N]^{k}$ , so [L3] gives $(\binom{m + n}{k}) = ∣ [M \cup N]^{k} ∣ = \sum_{i \in σ (k)} ∣ B_{i} ∣ = \sum_{i < σ (k)} (\binom{m}{i}) (\binom{n}{k - i})$ , using step 2.1 and the bridge for an index set that is a natural number.

step 1.1step 1.2step 2.1L3

4.1

No range restriction is needed: if $i > m$ then $[M]^{i} = \emptyset$ and $(\binom{m}{i}) = 0$ , and if $k - i > n$ then $(\binom{n}{k - i}) = 0$ , so those blocks are empty and contribute nothing, exactly as the identity says.

step 2.1step 3.1L1∎

Remarks

Why disjointness is arranged rather than assumed. The counting argument needs $M$ and $N$ disjoint, and two arbitrary sets of cardinalities $m$ and $n$ need not be. Replacing them by $m \times {0}$ and $n \times {1}$ costs one line and the transport clause of The cardinality $∣ A ∣$ of a finite set, and it is what makes the sum rule applicable.
Not by generating functions, and not by comparing coefficients. Both of the usual quick proofs need machinery that is far later in the reading order: formal power series in the first case, and a polynomial ring in the second. The double count needs neither.
Pascal's rule is the special case $m = 1$ , read through $(\binom{1}{0}) = (\binom{1}{1}) = 1$ and $(\binom{1}{i}) = 0$ for $i \geq 2$ : for $k \geq 1$ the identity collapses to $(\binom{1 + n}{k}) = (\binom{n}{k}) + (\binom{n}{k - 1})$ , while at $k = 0$ the sum has the single term $(\binom{1}{0}) (\binom{n}{0}) = 1 = (\binom{n + 1}{0})$ . The restriction $k \geq 1$ is not cosmetic: $n - m$ is the truncated difference throughout this page (Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ ), so writing the collapsed identity at $k = 0$ would read $(\binom{n}{0 - 1})$ as $(\binom{n}{0}) = 1$ and assert $1 = 1 + 1$ .

Depends on

Used by

Vandermonde's identity checked at m = 4, n = 3, k = 3, both sides equal to 35 Example

Dependency tree · two levels

39 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Vandermonde's identity (Wikipedia) (standard reference, not scraped)
Binomial coefficient (Wikipedia) (standard reference, not scraped)
Bijective proof (Wikipedia) (standard reference, not scraped)

Vandermonde's identity (m+nk)=∑i<k+1(mi)(nk−i)(km+n​)=∑i<k+1​(im​)(k−in​)