AFTD Auto-Formalizing Theoretical Domains

sum_range_sum_range_swap

theoremverified

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

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.

  1. 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.

    line 5

    uses Finset.mul_sum

      simp_rw [Finset.mul_sum]
  2. 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.

    lines 6–7

    uses Finset.sum_comm', mul_comm

      rw [Finset.sum_comm' (t' := Finset.range (d + 1)) (s' := fun j => Finset.range (min (d - j) (d - 1) + 1))]
      · simp_rw [mul_comm]
  3. 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.

    lines 8–9

    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]
  4. 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.

    line 10

        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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it