TheoremStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck 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 \le n}\binom{i}{k} = \binom{n+1}{k+1}$

Statement

For all $n, k \in \mathbb{N}$ :

Pascal's rule. $\displaystyle\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$ , with no restriction relating $k$ to $n$ ;
The hockey-stick identity. $\displaystyle\sum_{i<n+1}\binom{i}{k} = \binom{n+1}{k+1}$ , the sum being the $\mathbb{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 $\mathbb{N}$ over $i = 0, 1, \dots, n$ .

Facts & Assumptions

Given: Naturals $n$ , $k$ ; $\sigma(m) = m+1$ ; and $\binom{m}{j} = \lvert [X]^{j}\rvert$ for any finite $X$ with $\lvert X\rvert = 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} := \lvert [n]^{k}\rvert$ ): $\lvert [X]^{j}\rvert = \binom{\lvert X\rvert}{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<\sigma(n)} c_i = \sum_{i<n} c_i + c_n$ (The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$ , 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 $\mathbb{N}$ ).

[L4]

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

[L5]

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

[L6]

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

[L7]

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

Proof

technique · induction

1.1

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

L3L4L5L7

1.2

The two blocks are counted by $\binom{n}{k}$ and $\binom{n}{\sigma(k)}$ . First, $Q = [A']^{\sigma(k)}$ , since a subset of $A$ avoiding $a$ is exactly a subset of $A'$ ; so $\lvert Q\rvert = \binom{n}{\sigma(k)}$ by [L2]. Second, $S \mapsto S \setminus \{a\}$ maps $P$ into $[A']^{k}$ : for $S \in P$ the set $S$ is the disjoint union of $S\setminus\{a\}$ and $\{a\}$ , so $\sigma(k) = \lvert S\setminus\{a\}\rvert + 1$ and $\lvert S\setminus\{a\}\rvert = k$ by [L5]. Its two-sided inverse is $T \mapsto T \cup \{a\}$ , which lands in $P$ because $a \notin T \subseteq A'$ gives $\lvert T \cup \{a\}\rvert = k+1 = \sigma(k)$ by [L3]. Hence $\lvert P\rvert = \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}{\sigma(k)}$ . If $k = 0$ both are $1$ , by $\binom{0}{0} = 1$ and $\binom{1}{1} = 1$ from [L2]. If $k \ge 1$ then $k > 0$ and $\sigma(k) > 1$ , so both are $0$ by [L2].

baseL2L3L5

1.4

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

2.1

Clause 1. By step 1.1, step 1.2 and the sum rule, $\binom{\sigma(n)}{\sigma(k)} = \big\lvert [A]^{\sigma(k)}\big\rvert = \lvert P\rvert + \lvert Q\rvert = \binom{n}{k} + \binom{n}{\sigma(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{\sigma(n)}{1} = 1 + \binom{n}{1}$ , which is $\sigma(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<\sigma(\sigma(n))}\binom{i}{k} = \sum_{i<\sigma(n)}\binom{i}{k} + \binom{\sigma(n)}{k} = \binom{\sigma(n)}{\sigma(k)} + \binom{\sigma(n)}{k}$ , and clause 1 applied with $\sigma(n)$ in place of $n$ says exactly that this is $\binom{\sigma(\sigma(n))}{\sigma(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} := \lvert [n]^{k}\rvert$ 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 \ge 1$ have to be separated.
Everything here is an identity in $\mathbb{N}$ . No embedding into $\mathbb{R}$ is used or needed; the sum is the $\mathbb{N}$ -valued one.

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 75 results over 27 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click 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)\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}(k+1n+1​)=(kn​)+(k+1n​), and the hockey-stick identity ∑i≤n(ik)=(n+1k+1)\sum_{i \le n}\binom{i}{k} = \binom{n+1}{k+1}∑i≤n​(ki​)=(k+1n+1​)