AFTD Auto-Formalizing Theoretical Domains

sum_ballot_weight_eq

theoremverified

For natural numbers $d$ and $a$ with $a \le d - 1$, the sum $\sum_{s \in \text{range}(a + 1)} \text{ballot\_weight}(2d - 1, s)$ equals $\binom{2d-1}{a}$.

Statement

theorem sum_ballot_weight_eq (d a : ℕ) (ha : a ≤ d - 1) :
    ∑ s ∈ Finset.range (a + 1), ballot_weight (2 * d - 1) s = (2 * d - 1).choose a
Source
arXiv:2611.06860 "Largest Sperner families with bounded VC-dimension", Lemma 2.5
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • ballot_weightThe function ballot_weight taking two natural numbers $p$ and $k$ and returning the natural number defined as: if $k = 0$ then…
Used by 1

Read back from the Lean

For all natural numbers d and a, if a ≤ d - 1, then the sum over s from 0 to a (i.e., s ∈ Finset.range (a + 1)) of ballot_weight (2 * d - 1) s equals Nat.choose (2 * d - 1) a, where ballot_weight p k is Nat.choose p 0 if k = 0, and (Nat.choose p k - Nat.choose p (k - 1)) otherwise (with 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 induction on $a$. The base case $a = 0$ follows immediately from the definition of ballot weight. For the induction step, the sum up to $a + 1$ is split into the sum up to $a$ plus the $(a+1)$-th term, and the induction hypothesis replaces the sum with $\binom{2d-1}{a}$. Since $a + 1 \le d - 1$, the index $a$ is strictly below the midpoint $(2d - 1) / 2$, which guarantees $\binom{2d-1}{a} \le \binom{2d-1}{a+1}$ and allows natural number subtraction to cancel the terms to yield $\binom{2d-1}{a+1}$.

  1. The base case $a = 0$ holds: $\sum_{s \in \text{range}(1)} \text{ballot\_weight}(2d - 1, s) = \binom{2d-1}{0}$.

    We proceed by induction on $a$. For $a = 0$, the range contains only the single index $s = 0$. By definition, $\text{ballot\_weight}(2d - 1, 0) = \binom{2d-1}{0}$, so simplification confirms the base case directly.

    lines 4–6

      induction a with
      | zero =>
          simp [ballot_weight]
  2. The inductive step reduces to showing $\binom{2d-1}{a} + \left(\binom{2d-1}{a+1} - \binom{2d-1}{a}\right) = \binom{2d-1}{a+1}$.

    Assuming $a + 1 \le d - 1$, we also have $a \le d - 1$, which allows us to apply the induction hypothesis. Using `Finset.sum_range_succ`, we separate the final term $s = a + 1$ from the sum and rewrite the preceding sum as $\binom{2d-1}{a}$. Because $a + 1 \neq 0$, the definition of $\text{ballot\_weight}$ simplifies the last term to $\binom{2d-1}{a+1} - \binom{2d-1}{a}$.

    lines 7–10

    uses Finset.sum_range_succ

      | succ a ih =>
          have ha_prev : a ≤ d - 1 := by omega
          rw [Finset.sum_range_succ, ih ha_prev]
          simp [ballot_weight]
  3. The binomial coefficients satisfy $\binom{2d-1}{a} \le \binom{2d-1}{a+1}$.

    From $a + 1 \le d - 1$, linear arithmetic gives $a < (2d - 1) / 2$. By `Nat.choose_le_succ_of_lt_half_left`, the sequence of binomial coefficients $\binom{n}{r}$ is non-decreasing for $r < n / 2$, yielding the inequality.

    lines 11–12

    uses Nat.choose_le_succ_of_lt_half_left

          have hle : (2 * d - 1).choose a ≤ (2 * d - 1).choose (a + 1) := by
            exact Nat.choose_le_succ_of_lt_half_left (by omega)
  4. The equality $\binom{2d-1}{a} + \left(\binom{2d-1}{a+1} - \binom{2d-1}{a}\right) = \binom{2d-1}{a+1}$ holds, completing the inductive step.

    Having established $\binom{2d-1}{a} \le \binom{2d-1}{a+1}$, natural number subtraction does not truncate at zero, so the identity $y + (x - y) = x$ holds. Linear arithmetic (`omega`) closes the goal.

    line 13

          omega
Finset.sum_range_succ
The sum of a function over the range $\{0, \dots, n\}$ equals the sum over $\{0, \dots, n - 1\}$ plus the term at $n$.
Nat.choose_le_succ_of_lt_half_left
For natural numbers $r$ and $n$, if $r < n / 2$, then $\binom{n}{r} \le \binom{n}{r + 1}$.

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

/-- Telescoping sum of ballot weights up to rank a <= d - 1 equals the binomial coefficient (2d - 1).choose a. -/theorem sum_ballot_weight_eq (d a : ℕ) (ha : a ≤ d - 1) :    ∑ s ∈ Finset.range (a + 1), ballot_weight (2 * d - 1) s = (2 * d - 1).choose a := by  induction a with  | zero =>      simp [ballot_weight]  | succ a ih =>      have ha_prev : a ≤ d - 1 := by omega      rw [Finset.sum_range_succ, ih ha_prev]      simp [ballot_weight]      have hle : (2 * d - 1).choose a ≤ (2 * d - 1).choose (a + 1) := by        exact Nat.choose_le_succ_of_lt_half_left (by omega)      omega
See it in the graphDiscuss this resultChallenge it