sum_ballot_weight_eq
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
- sum_ballot_weight_min_eqFor natural numbers $d$ and $j$ with $1 \le d$ and $j \le d$, the sum…
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}$.
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.
induction a with | zero => simp [ballot_weight]
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}$.
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]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.
uses
Nat.choose_le_succ_of_lt_half_lefthave hle : (2 * d - 1).choose a ≤ (2 * d - 1).choose (a + 1) := by exact Nat.choose_le_succ_of_lt_half_left (by omega)
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.
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}$.
- In Lean, subtraction on natural numbers truncates at zero ($a - b = 0$ whenever $a < b$). Consequently, the algebraic cancellation $y + (x - y) = x$ requires the side condition $y \le x$ (established in lines 11–12), whereas over the integers or reals the telescoping cancellation would be immediate.
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.
/-- 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