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.
for every and every
Statement
Let with and let . Then, in ,
where is the canonical natural (The canonical natural of a field), the binomial coefficients are the counts of The set of -element subsets and the binomial coefficient , and is the truncated difference of Finite sums and finite products of natural numbers, and in , which for is the ordinary one, so that .
The hypothesis is part of the statement. At and the left-hand side is , while the truncated difference gives and the right-hand side is .
Two readings worth recording. At both sides are , since . For both sides are : the terms of the left-hand side with vanish and the remaining sum is the full alternating row sum of , which vanishes because , while because .
Facts & Assumptions
Given: Naturals and ; the abbreviation , so that (Finite sums and finite products of natural numbers, and in , Order on the natural numbers); the real finite sum of Finite sums and finite products, by recursion; and integer powers (Integer powers ) in the ordered field (Ordered field, Field).
Induction: a property holding at and inherited by successors holds at every natural (The principle of mathematical induction).
Recursion clauses of the real finite sum: and (Finite sums and finite products, by recursion, Laws of finite sums and finite products).
Pascal's rule, with no restriction relating the two indices: for all (Pascal's rule , and the hockey-stick identity , clause 1).
for every (The set of -element subsets and the binomial coefficient ); and is additive (Laws of finite sums and products in , and , clause 0, The canonical natural of a field).
Powers of : and (Integer powers ).
Proof
Fix and write , so that ; the claim is proved by induction on , for this fixed .
Base case . By [L2] the left-hand side is the single term , which is by [L4] and [L5]; and the right-hand side is for the same reason.
Inductive hypothesis: fix and assume .
Pascal's rule at and , together with , gives , hence by the additivity of .
By the recursion clause of [L2] and the hypothesis of step 1.3, .
Substituting step 1.4 into step 2.1 and using from [L5]: .
So the claim holds at whenever it holds at , and it holds at ; by [L1] it holds for every , for the fixed , which was arbitrary.
Remarks
-
Where is spent. In exactly one place: the identity , which is what lets Pascal's rule be applied with upper index . Under the truncated difference the equation fails at , where and , and the statement fails there too.
-
Why not the full alternating row sum. The published corollary of the binomial theorem gives the sum over the whole row, and only for . A truncation of that row is a different quantity, and the identity above is what says how far a truncation misses: by exactly one binomial coefficient of the row above, with the sign of the last term kept.
Depends on
- 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}$
- The set $[A]^{k}$ of $k$-element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$
- The canonical natural $\iota(n) = n \cdot 1_F$ of a field
- Integer powers $a^m$
- Finite sums and finite products, by recursion
- Laws of finite sums and finite products
- Laws of finite sums and products in $\mathbb{N}$, and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$
- Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$
- The principle of mathematical induction
- Order on the natural numbers
- Ordered field
- Field
Used by
- The conventions this page fixes: the empty intersection, where the counts live, the first index of every sum, and what the declared prerequisites do not supply Remark
- Truncating the sieve at an odd depth over-estimates the size of the union and truncating it at an even depth under-estimates it Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 83 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
- Binomial coefficient (Wikipedia) (standard reference, not scraped)
- Pascal's rule (Wikipedia) (standard reference, not scraped)
- Inclusion-exclusion principle (Wikipedia) (standard reference, not scraped)
- Indicator Functions and Inclusion-Exclusion (University of South Carolina notes) (standard reference, not scraped)