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

A finite sum is unchanged by a permutation of its index range: $\sum_{k < n} a_{π (k)} = \sum_{k < n} a_{k}$ for every bijection $π : n \to n$

Statement

Let $n \in N$ and let $π : n \to n$ be a bijection (Injection, surjection, bijection). Then:

for every list $a : n \to R$ , $\sum_{k < n} a_{π (k)} = \sum_{k < n} a_{k}$ and $\prod_{k < n} a_{π (k)} = \prod_{k < n} a_{k}$ (Finite sums and finite products, by recursion);
for every list $a : n \to N$ , $\sum_{k < n} a_{π (k)} = \sum_{k < n} a_{k}$ and $\prod_{k < n} a_{π (k)} = \prod_{k < n} a_{k}$ (Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ ).

This is not in Laws of finite sums and finite products. That item proves additivity, scaling, splitting, monotonicity, telescoping and the product laws, and states no invariance clause; the same is true of the $N$ -valued list on this page. Permutation invariance is exactly what makes a sum over a finite set of indices well posed, which is the next item, so it is proved here first.

Facts & Assumptions

Given: A natural number $n$ , a bijection $π : n \to n$ , and a list $a$ of length $n$ . Throughout, $σ (n) = n \cup {n}$ , $n = {k : k < n}$ , and $*$ denotes any one of the four operations $(R, +)$ , $(R, \cdot)$ , $(N, +)$ , $(N, \cdot)$ , with $e$ the corresponding identity element $0$ , $1$ , $0$ , $1$ . Write $★_{k < n} c_{k}$ for the associated iterated operation, that is, for $\sum_{k < n} c_{k}$ in the two additive cases and $\prod_{k < n} c_{k}$ in the two multiplicative ones.

[L1]

Induction (The principle of mathematical induction).

[L2]

The four iterated operations obey the same two recursion clauses: $★_{k < 0} c_{k} = e$ and $★_{k < σ (n)} c_{k} = (★_{k < n} c_{k}) * c_{n}$ (Finite sums and finite products, by recursion, Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ ).

[L3]

Each of the four operations is associative and commutative on its set and has $e$ as a two-sided identity (Field, Ordered field for $R$ ; Addition is associative, Addition is commutative, Multiplication is associative, Multiplication is commutative, Left identity for addition, Zero and one under multiplication for $N$ ). These three properties are the only facts about $*$ used below, which is why one argument proves all four clauses.

[L4]

Order and membership: $k < n ⟺ k \in n$ , $n = {k : k < n}$ , $k < σ (n) ⟺ k \leq n$ , $n \notin n$ , and $σ (n) ∖ {n} = n$ (On $N$ the order is membership: $m < n ⟺ m \in n$ , The natural numbers $N$ (von Neumann), Order on the natural numbers).

[L5]

Discreteness and successors: $m < n ⟺ σ (m) \leq n$ ; every nonzero natural is $σ (s)$ for a unique $s$ (Discreteness: $σ (n)$ is the immediate successor, Every nonzero natural number is a successor, The von Neumann naturals form a Peano system).

[L6]

Maps: a composite of bijections is a bijection; a bijection restricted to a subset of its domain is a bijection onto the image of that subset (Injection, surjection, bijection).

Proof

technique · induction

1.1

For $n \in N$ and $j \leq n$ define $d_{j}^{n} : n \to σ (n)$ by $d_{j}^{n} (k) = k$ for $k < j$ and $d_{j}^{n} (k) = σ (k)$ for $j \leq k < n$ ; this is the increasing enumeration of $σ (n) ∖ {j}$ . It is a bijection of $n$ onto $σ (n) ∖ {j}$ : its values lie in $σ (n)$ and avoid $j$ , since $k < j$ in the first clause and $σ (k) > k \geq j$ in the second; it is injective, being strictly increasing on each clause and satisfying $k < j \leq σ (k^{'})$ across them; and it is surjective, since $t \in σ (n)$ with $t < j$ has $t < n$ and $d_{j}^{n} (t) = t$ , while $t > j$ is nonzero, so $t = σ (s)$ with $j \leq s$ by [L5] and $s < n$ because $σ (s) \leq n$ , giving $d_{j}^{n} (s) = t$ .

L4L5L6construct

1.2

Claim $(A)$ at $n = 0$ : for a list $c$ of length $σ (0) = 1$ and the only admissible index $j = 0$ , both sides of $(A)$ read $c_{0}$ , since $★_{k < 1} c_{k} = e * c_{0} = c_{0}$ and $(★_{k < 0} c_{d_{0}^{0} (k)}) * c_{0} = e * c_{0} = c_{0}$ .

baseL2L3

1.3

Inductive hypothesis for $(A)$ : fix $n$ and assume that for every list $c$ of length $σ (n)$ and every $j \leq n$ one has $★_{k < σ (n)} c_{k} = (★_{k < n} c_{d_{j}^{n} (k)}) * c_{j}$ .

1.4

The main claim at $n = 0$ : the only bijection $0 \to 0$ is the empty map and both sides are the empty iterate $e$ .

2.1

Inductive step for $(A)$ . Let $c$ be a list of length $σ (σ (n))$ and let $j \leq σ (n)$ . If $j = σ (n)$ then $d_{j}^{σ (n)}$ is the identity of $σ (n)$ , so the right-hand side is $(★_{k < σ (n)} c_{k}) * c_{σ (n)}$ , which is the left-hand side by [L2]. If instead $j \leq n$ , apply the hypothesis of step 1.3 to the restriction of $c$ to $σ (n)$ to get $★_{k < σ (n)} c_{k} = (★_{k < n} c_{d_{j}^{n} (k)}) * c_{j}$ ; hence $★_{k < σ (σ (n))} c_{k} = ((★_{k < n} c_{d_{j}^{n} (k)}) * c_{j}) * c_{σ (n)} = ((★_{k < n} c_{d_{j}^{n} (k)}) * c_{σ (n)}) * c_{j}$ by [L3]. Finally $d_{j}^{σ (n)}$ agrees with $d_{j}^{n}$ on $n$ and sends $n$ to $σ (n)$ , because $j \leq n$ , so the inner bracket is $★_{k < σ (n)} c_{d_{j}^{σ (n)} (k)}$ by [L2], which is the right-hand side at $σ (n)$ .

step 1.3L2L3

3.1

Claim $(A)$ therefore holds for every $n$ : for every list $c$ of length $σ (n)$ and every $j \leq n$ , $★_{k < σ (n)} c_{k} = (★_{k < n} c_{d_{j}^{n} (k)}) * c_{j}$ . Informally, any single entry may be moved to the end without changing the value.

step 1.2step 2.1L1

4.1

Inductive step for the main claim. Assume it at $n$ , for every list of length $n$ and every bijection of $n$ . Let $π : σ (n) \to σ (n)$ be a bijection, let $a$ be a list of length $σ (n)$ , and put $j : = π^{- 1} (n) \leq n$ . Applying $(A)$ to the list $c_{k} : = a_{π (k)}$ at the index $j$ gives $★_{k < σ (n)} a_{π (k)} = (★_{k < n} a_{ρ (k)}) * a_{π (j)}$ with $ρ : = π \circ d_{j}^{n}$ and $a_{π (j)} = a_{n}$ . Now $ρ$ is a bijection of $n$ onto $n$ : $d_{j}^{n}$ is a bijection of $n$ onto $σ (n) ∖ {j}$ by step 1.1, and $π$ restricts to a bijection of $σ (n) ∖ {j}$ onto $σ (n) ∖ {n} = n$ . So the inductive hypothesis applies to $ρ$ and gives $★_{k < n} a_{ρ (k)} = ★_{k < n} a_{k}$ , whence $★_{k < σ (n)} a_{π (k)} = (★_{k < n} a_{k}) * a_{n} = ★_{k < σ (n)} a_{k}$ .

step 1.1step 3.1assume-hypL2L4L6

5.1

By induction the main claim holds for every $n \in N$ , every list of length $n$ and every bijection $π : n \to n$ .

step 1.4step 4.1L1

6.1

Since $*$ was any one of the four operations of the Given, and [L3] holds for each of them, step 5.1 is exactly clauses 1 and 2.

step 5.1L3discharge-induction∎

Remarks

Where the deletion map earns its keep. The usual textbook proof says "move the term $a_{n}$ to the end and delete it", and leaves the resulting map on the shorter index range unexamined. That map is $d_{j}^{n}$ composed with $π$ , and checking that it really is a bijection of $n$ onto $n$ is the only place where anything can go wrong; step 1.1 writes it down and verifies it in both directions.
One proof, four statements. Only associativity, commutativity, the identity and the two recursion clauses are used, so the argument is indifferent to which of the four operations is meant. The same observation is what later licenses the identical statement in an arbitrary monoid, where it belongs; nothing here needs that generality.
No choice is used. The index $j = π^{- 1} (n)$ is determined, not selected, because $π$ is a bijection.

Depends on

Used by

Dependency tree · two levels

43 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

Permutation (Wikipedia) (standard reference, not scraped)
Summation (Wikipedia) (standard reference, not scraped)
T. Tao, Analysis I, 3rd ed., §7.1 (standard reference, not scraped)

A finite sum is unchanged by a permutation of its index range: ∑k<naπ(k)=∑k<nak∑k<n​aπ(k)​=∑k<n​ak​ for every bijection π:n→nπ:n→n