TheoremStatement: AI-adaptedProof: 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.

Pascal's rule $(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})$ , and the hockey-stick identity $\sum_{i \leq n} (\binom{i}{k}) = (\binom{n + 1}{k + 1})$

Statement

For all $n, k \in N$ :

Pascal's rule. $(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})$ , with no restriction relating $k$ to $n$ ;
The hockey-stick identity. $\sum_{i < n + 1} (\binom{i}{k}) = (\binom{n + 1}{k + 1})$ , the sum being the $N$ -valued finite sum of Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ over $i = 0, 1, \dots, n$ .

Facts & Assumptions

Given: Naturals $n$ , $k$ ; $σ (m) = m + 1$ ; and $(\binom{m}{j}) = ∣ [X]^{j} ∣$ for any finite $X$ with $∣ X ∣ = m$ .

[L1]

Induction (The principle of mathematical induction).

[L2]

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

[L3]

The sum rule for two disjoint blocks, and the recursion clause $\sum_{i < σ (n)} c_{i} = \sum_{i < n} c_{i} + c_{n}$ (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, Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ ).

[L4]

Cardinality (The cardinality $∣ A ∣$ of a finite set, A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ): transport along a bijection; a subset of a finite set is finite; $∣ {a} ∣ = 1$ ; $∣ X ∣ = 0$ exactly when $X = \emptyset$ .

[L5]

Cancellation and order in $N$ : $x + 1 = y + 1$ implies $x = y$ ; trichotomy (Addition is cancellative, Trichotomy of the order on $N$ , Order on the natural numbers).

[L6]

Maps (Injection, surjection, bijection): a map with a two-sided inverse is a bijection.

[L7]

Naturals: $σ (m) = m \cup {m}$ and $m \notin m$ (The natural numbers $N$ (von Neumann)).

Proof

technique · induction

1.1

Fix $n$ and $k$ , let $A$ be a set with $∣ A ∣ = σ (n)$ , and fix $a \in A$ , possible because $A \neq \emptyset$ by [L4]. Put $A^{'} : = A ∖ {a}$ , which is finite with $∣ A^{'} ∣ = n$ : indeed $A = A^{'} \cup {a}$ is a disjoint union, so $σ (n) = ∣ A^{'} ∣ + 1$ by [L3], and [L5] applies. Split $[A]^{σ (k)}$ into $P : = {S \in [A]^{σ (k)} : a \in S}$ and $Q : = {S \in [A]^{σ (k)} : a \notin S}$ , which are disjoint with union $[A]^{σ (k)}$ .

L3L4L5L7

1.2

The two blocks are counted by $(\binom{n}{k})$ and $(\binom{n}{σ (k)})$ . First, $Q = [A^{'}]^{σ (k)}$ , since a subset of $A$ avoiding $a$ is exactly a subset of $A^{'}$ ; so $∣ Q ∣ = (\binom{n}{σ (k)})$ by [L2]. Second, $S \mapsto S ∖ {a}$ maps $P$ into $[A^{'}]^{k}$ : for $S \in P$ the set $S$ is the disjoint union of $S ∖ {a}$ and ${a}$ , so $σ (k) = ∣ S ∖ {a} ∣ + 1$ and $∣ S ∖ {a} ∣ = k$ by [L5]. Its two-sided inverse is $T \mapsto T \cup {a}$ , which lands in $P$ because $a \notin T \subseteq A^{'}$ gives $∣ T \cup {a} ∣ = k + 1 = σ (k)$ by [L3]. Hence $∣ P ∣ = (\binom{n}{k})$ by [L2] and [L4].

L2L3L4L5L6construct

1.3

Base case of clause 2, at $n = 0$ . The left-hand side is $\sum_{i < 1} (\binom{i}{k}) = (\binom{0}{k})$ by [L3], and the right-hand side is $(\binom{1}{σ (k)})$ . If $k = 0$ both are $1$ , by $(\binom{0}{0}) = 1$ and $(\binom{1}{1}) = 1$ from [L2]. If $k \geq 1$ then $k > 0$ and $σ (k) > 1$ , so both are $0$ by [L2].

baseL2L3L5

1.4

Inductive hypothesis for clause 2: fix $n$ and assume $\sum_{i < σ (n)} (\binom{i}{k}) = (\binom{σ (n)}{σ (k)})$ for every $k$ .

2.1

Clause 1. By step 1.1, step 1.2 and the sum rule, $(\binom{σ (n)}{σ (k)}) = ∣ [A]^{σ (k)} ∣ = ∣ P ∣ + ∣ Q ∣ = (\binom{n}{k}) + (\binom{n}{σ (k)})$ . No relation between $k$ and $n$ was used, and the identity is correct beyond the range as well: for $k > n$ all three coefficients are $0$ by [L2], and at $k = 0$ it reads $(\binom{σ (n)}{1}) = 1 + (\binom{n}{1})$ , which is $σ (n) = 1 + n$ .

step 1.1step 1.2L2L3

3.1

Inductive step for clause 2. Using the recursion clause and then the hypothesis of step 1.4, $\sum_{i < σ (σ (n))} (\binom{i}{k}) = \sum_{i < σ (n)} (\binom{i}{k}) + (\binom{σ (n)}{k}) = (\binom{σ (n)}{σ (k)}) + (\binom{σ (n)}{k})$ , and clause 1 applied with $σ (n)$ in place of $n$ says exactly that this is $(\binom{σ (σ (n))}{σ (k)})$ .

step 1.4step 2.1L3

4.1

By step 1.3, step 3.1 and induction, clause 2 holds for every $n$ and every $k$ .

step 1.3step 3.1L1

5.1

Clause 1 is step 2.1 and clause 2 is step 4.1.

step 2.1step 4.1discharge-induction∎

Remarks

The rule needs no range hypothesis because the boundary values of The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ make every out-of-range coefficient $0$ rather than undefined. Both edges were checked in step 2.1 rather than assumed.
The hockey stick sums a column, not a row. The index $i$ runs over $0, 1, \dots, n$ with $k$ fixed, and the terms with $i < k$ vanish, so the identity is a statement about the entries $(\binom{k}{k}), (\binom{k + 1}{k}), \dots$ of one column of Pascal's triangle. The base case $n = 0$ is the only place where the two readings $k = 0$ and $k \geq 1$ have to be separated.
Everything here is an identity in $N$ . No embedding into $R$ is used or needed; the sum is the $N$ -valued one.

Depends on

Used by

Dependency tree · two levels

50 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

Pascal's rule (Wikipedia) (standard reference, not scraped)
Hockey-stick identity (Wikipedia) (standard reference, not scraped)
Pascal's triangle (Wikipedia) (standard reference, not scraped)

Pascal's rule (n+1k+1)=(nk)+(nk+1)(k+1n+1​)=(kn​)+(k+1n​), and the hockey-stick identity ∑i≤n(ik)=(n+1k+1)∑i≤n​(ki​)=(k+1n+1​)