sum_range_sum_range_swap
For any positive integer $d$ and functions $f, g : ℕ → ℕ$, the summation identity $\sum_{s=0}^{d-1} f(s) \sum_{j=0}^{d-s} g(j) = \sum_{j=0}^d g(j) \sum_{s=0}^{\min(d-j, d-1)} f(s)$ holds.
Statement
theorem sum_range_sum_range_swap (d : ℕ) (hd : 1 ≤ d) (f g : ℕ → ℕ) :
∑ s ∈ Finset.range d, f s * (∑ j ∈ Finset.range (d - s + 1), g j) =
∑ j ∈ Finset.range (d + 1), g j * (∑ s ∈ Finset.range (min (d - j) (d - 1) + 1), f s)- Source
- arXiv:2611.06860 "Largest Sperner families with bounded VC-dimension", Lemma 2.5
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- binomial_convolution_restricted_weightsFor natural numbers $d$ and $n$ with $1 \le d$ and $2d - 1 \le n$, the double sum…
Read back from the Lean
For any natural number d such that 1 ≤ d, and any functions f, g : ℕ → ℕ, ∑_{s ∈ Finset.range d} f(s) * (∑_{j ∈ Finset.range (d - s + 1)} g(j)) = ∑_{j ∈ Finset.range (d + 1)} g(j) * (∑_{s ∈ Finset.range (min (d - j) (d - 1) + 1)} f(s)) In other words, the sum over s ∈ {0, …, d - 1} of f(s) times the sum over j ∈ {0, …, d - s} of g(j) equals the sum over j ∈ {0, …, d} of g(j) times the sum over s ∈ {0, …, min(d - j, d - 1)} of f(s) (with all subtractions being truncated natural number subtraction).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The identity is proved by distributing the outer factors into the inner sums and interchanging the summation order using `Finset.sum_comm'`. Commuting the factors in the summand matches the right-hand side, leaving only the obligation that the two index regions coincide. Translating range memberships into inequalities and applying linear integer arithmetic (`omega`) confirms that s < d ∧ j ≤ d - s is equivalent to s ≤ min(d - j, d - 1) ∧ j ≤ d when 1 ≤ d.
The products are distributed into the inner sums on both sides of the identity.
Applying `Finset.mul_sum` moves the factor f(s) inside the inner sum over j on the left-hand side, and moves g(j) inside the inner sum over s on the right-hand side. Both sides are now double sums of products f(s) * g(j) and g(j) * f(s) respectively.
uses
Finset.mul_sumsimp_rw [Finset.mul_sum]
Interchanging the summation order on the left-hand side matches the right-hand side, reducing the theorem to checking that the summation regions coincide.
Using `Finset.sum_comm'`, the double sum on the left is rewritten with the order of summation swapped, indexing over j ∈ [0, d] outer and s ∈ [0, min(d - j, d - 1)] inner. Commuting the multiplicands via `mul_comm` makes the summands identical to the right-hand side, leaving only the side condition that a pair (s, j) belongs to the original summation domain if and only if it belongs to the swapped domain.
uses
Finset.sum_comm',mul_commrw [Finset.sum_comm' (t' := Finset.range (d + 1)) (s' := fun j => Finset.range (min (d - j) (d - 1) + 1))] · simp_rw [mul_comm]
The domain membership condition is rewritten in terms of inequalities on s and j.
Fixing arbitrary indices s and j, membership in `Finset.range` is translated into inequalities (`Finset.mem_range`). The successor inequalities < k + 1 are replaced by ≤ k (`Nat.lt_succ_iff`), and the upper bound on the minimum is split into a conjunction (`le_min_iff`), yielding the equivalence s < d ∧ j ≤ d - s ↔ (s ≤ d - j ∧ s ≤ d - 1) ∧ j ≤ d.
uses
Finset.mem_range,Nat.lt_succ_iff,le_min_iff· intro s j simp only [Finset.mem_range, Nat.lt_succ_iff, le_min_iff]
The index inequalities for the two summation domains are equivalent. automation
Since 1 ≤ d, the condition s < d is equivalent to s ≤ d - 1. For natural numbers, j ≤ d - s is equivalent to s + j ≤ d, which in turn is equivalent to s ≤ d - j and j ≤ d. The decision procedure `omega` closes this linear integer arithmetic goal.
omega
Finset.mul_sum- Multiplication distributes over finite sums from the left: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_comm'- Two double sums over dependent finite sets are equal if the conditions for indices being in the respective index sets are logically equivalent.
mul_comm- Multiplication is commutative: a * b = b * a.
Finset.mem_range- A natural number m belongs to `Finset.range n` if and only if m < n.
Nat.lt_succ_iff- For natural numbers, m < n + 1 if and only if m ≤ n.
le_min_iff- An element c is less than or equal to min a b if and only if c ≤ a and c ≤ b.
- The arithmetic equivalence between the index domains s < d ∧ j ≤ d - s and (s ≤ d - j ∧ s ≤ d - 1) ∧ j ≤ d is discharged by Lean's Presburger arithmetic decision procedure (`omega`).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Interchange the order of summation in a triangular double sum over finite ranges. -/theorem sum_range_sum_range_swap (d : ℕ) (hd : 1 ≤ d) (f g : ℕ → ℕ) : ∑ s ∈ Finset.range d, f s * (∑ j ∈ Finset.range (d - s + 1), g j) = ∑ j ∈ Finset.range (d + 1), g j * (∑ s ∈ Finset.range (min (d - j) (d - 1) + 1), f s) := by simp_rw [Finset.mul_sum] rw [Finset.sum_comm' (t' := Finset.range (d + 1)) (s' := fun j => Finset.range (min (d - j) (d - 1) + 1))] · simp_rw [mul_comm] · intro s j simp only [Finset.mem_range, Nat.lt_succ_iff, le_min_iff] omega