CorollaryStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29

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.

$\sum_{k<n+1}\binom{n}{k} = 2^{n}$ , and $\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0$ for $n \ge 1$

Statement

The row sum. For every $n \in \mathbb{N}$ , in $\mathbb{N}$ , $\sum_{k<n+1}\binom{n}{k} = 2^{\,n} .$
The alternating row sum. For every $n \ge 1$ , in $\mathbb{R}$ , $\sum_{k<n+1}(-1)^{k}\,\iota\binom{n}{k} = 0 .$

Clause 2 is false at $n = 0$ , where the sum has the single term $(-1)^{0}\iota\binom{0}{0} = 1$ . The hypothesis $n \ge 1$ is therefore part of the statement, and this page's companion records the version that drops it as a false statement.

Facts & Assumptions

Given: A natural $n$ , a finite set $A$ with $\lvert A\rvert = n$ , and $\iota$ the canonical natural (The canonical natural $\iota(n) = n \cdot 1_F$ of a field).

[L1]

The binomial theorem: $(x+y)^{n} = \sum_{k<\sigma(n)}\iota\binom{n}{k}x^{k}y^{\,n-k}$ for reals $x$ , $y$ (The binomial theorem in $\mathbb{R}$ : $(x+y)^{n} = \sum_{k<n+1} \iota\!\binom{n}{k}\, x^{k} y^{\,n-k}$ ).

[L2]

$\lvert\mathcal{P}(A)\rvert = 2^{\,n}$ ( $\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ for finite $A$ ), and $\lvert [A]^{k}\rvert = \binom{n}{k}$ , with $[A]^{k} = \varnothing$ for $k > n$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $\binom{n}{k} := \lvert [n]^{k}\rvert$ ).

[L3]

The sum rule for a partition indexed by a finite set (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), the bridge $\sum_{i \in N} u_i = \sum_{k<N} u_k$ for an index set that is a natural number (The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form), and the $\mathbb{N}$ -valued recursion clauses (Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ ).

[L4]

$\iota$ is additive, multiplicative and injective, and $\iota\big(\sum^{\mathbb{N}}_{k<N} a_k\big) = \sum^{\mathbb{R}}_{k<N}\iota(a_k)$ (clauses 0, 6 and 7 of Laws of finite sums and products in $\mathbb{N}$ , and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$ ).

[L5]

Powers: $\iota(m^{j}) = \iota(m)^{j}$ (Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $\mathbb{R}$ , clause (d)); $a^{0} = 1$ and $a^{\sigma(j)} = a^{j}a$ , so $1^{j} = 1$ and $0^{j} = 0$ for $j \ge 1$ (Integer powers $a^m$ , Multiplication by zero: $0 \cdot a = 0$ , Field).

[L6]

Real finite sums: the recursion clauses and the scaling clause (Finite sums and finite products, by recursion, Laws of finite sums and finite products).

[L7]

Subsets of a finite set are finite and have cardinality at most $n$ (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$ , The cardinality $\lvert A\rvert$ of a finite set); induction (The principle of mathematical induction).

Proof

technique · direct

1.1

Clause 1, by counting. Every $S \subseteq A$ satisfies $\lvert S\rvert \le n$ by [L7], so $\mathcal{P}(A)$ is the union of the sets $[A]^{k}$ for $k \in \sigma(n) = \{0,1,\dots,n\}$ ; these are pairwise disjoint, since $S$ determines $\lvert S\rvert$ . By [L3] and [L2], $2^{\,n} = \lvert\mathcal{P}(A)\rvert = \sum_{k \in \sigma(n)}\big\lvert [A]^{k}\big\rvert = \sum_{k<\sigma(n)}\binom{n}{k}$ , the last equality being the bridge for an index set that is a natural number.

L2L3L7

1.2

Clause 2. Apply [L1] with $x = -1$ and $y = 1$ . The left-hand side is $(-1+1)^{n} = 0^{\,n}$ , which is $0$ because $n \ge 1$ ([L5]). The right-hand side is $\sum_{k<\sigma(n)}\iota\binom{n}{k}(-1)^{k}1^{\,n-k} = \sum_{k<\sigma(n)}(-1)^{k}\iota\binom{n}{k}$ , using $1^{j} = 1$ from [L5]. Hence the alternating sum is $0$ .

L1L5

2.1

Clause 1 again, from the binomial theorem, as a check that the two routes agree. Taking $x = y = 1$ in [L1] gives $(1+1)^{n} = \sum_{k<\sigma(n)}\iota\binom{n}{k}$ , and the right-hand side is $\iota\big(\sum^{\mathbb{N}}_{k<\sigma(n)}\binom{n}{k}\big)$ by the bridge clause of [L4], while the left-hand side is $\iota(2)^{n} = \iota(2^{\,n})$ by [L5]. Since $\iota$ is injective, $\sum^{\mathbb{N}}_{k<\sigma(n)}\binom{n}{k} = 2^{\,n}$ , which is step 1.1.

step 1.1L1L4L5

2.2

The hypothesis of clause 2 is not removable. At $n = 0$ the sum is $\sum_{k<1}(-1)^{k}\iota\binom{0}{k} = (-1)^{0}\iota\binom{0}{0} = 1 \cdot 1 = 1 \ne 0$ , by [L6], $\binom{0}{0} = 1$ and $a^{0} = 1$ . What fails in the argument of step 1.2 is exactly one thing: $(-1+1)^{0} = 0^{0} = 1$ rather than $0$ .

step 1.2L2L5L6

3.1

Clause 1 is step 1.1, confirmed by step 2.1; clause 2 is step 1.2, and step 2.2 shows why it carries the hypothesis $n \ge 1$ .

step 1.1step 1.2step 2.1step 2.2∎

Remarks

Two proofs of the same identity, deliberately. The counting proof is a statement about natural numbers and uses no embedding at all, while the analytic proof goes through $\mathbb{R}$ and comes back by the injectivity of $\iota$ . Recording both is what makes the agreement of the two readings visible rather than assumed.
Where the hypothesis of clause 2 is spent. In $0^{n} = 0$ , and nowhere else. The convention $0^{0} = 1$ is not a defect here: it is what makes the binomial theorem hold at $n = 0$ , and the price is that the alternating sum identity acquires a hypothesis. Both facts are consequences of the same convention.
The alternating sum is stated in $\mathbb{R}$ because $(-1)^{k}$ is not a natural number. The unsigned row sum, by contrast, is an identity between counts and is stated in $\mathbb{N}$ .

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 85 results over 29 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)
Binomial theorem (Wikipedia) (standard reference, not scraped)
Pascal's triangle (Wikipedia) (standard reference, not scraped)

∑k<n+1(nk)=2n\sum_{k<n+1}\binom{n}{k} = 2^{n}∑k<n+1​(kn​)=2n, and ∑k<n+1(−1)kι ⁣(nk)=0\sum_{k<n+1}(-1)^{k}\iota\!\binom{n}{k} = 0∑k<n+1​(−1)kι(kn​)=0 for n≥1n \ge 1n≥1