sum_ballot_weight_min_eq
For natural numbers $d$ and $j$ with $1 \le d$ and $j \le d$, the sum $\sum_{s \in \text{range}(\min(d-j, d-1) + 1)} \text{ballot\_weight}(2d - 1, s)$ equals $\binom{2d-1}{d-j}$.
Statement
theorem sum_ballot_weight_min_eq (d j : ℕ) (hd : 1 ≤ d) (hj : j ≤ d) :
∑ s ∈ Finset.range (min (d - j) (d - 1) + 1), ballot_weight (2 * d - 1) s =
(2 * d - 1).choose (d - j)- Source
- arXiv:2611.06860 "Largest Sperner families with bounded VC-dimension", Lemma 2.5
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- ballot_weightThe function ballot_weight taking two natural numbers $p$ and $k$ and returning the natural number defined as: if $k = 0$ then…
- sum_ballot_weight_eqFor 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…
- 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 all natural numbers $d$ and $j$, if $1 \le d$ and $j \le d$, then the sum of ballot_weight (2 * d - 1) s over $s \in \{0, \dots, \min(d - j, d - 1)\}$ is equal to $\binom{2d - 1}{d - j}$.
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 proof splits into cases based on whether $j = 0$ or $j > 0$. When $j > 0$, the minimum $\min(d - j, d - 1)$ is simply $d - j$, and the summation identity `sum_ballot_weight_eq` directly evaluates the sum to $\binom{2d - 1}{d - j}$. When $j = 0$, the minimum is $d - 1$, evaluating the sum to $\binom{2d - 1}{d - 1}$, which matches the goal $\binom{2d - 1}{d}$ by the symmetry of binomial coefficients.
We split the proof into two cases: $j = 0$ and $j > 0$.
Using `Nat.eq_zero_or_pos`, any natural number $j$ is either zero or strictly positive.
uses
Nat.eq_zero_or_posrcases Nat.eq_zero_or_pos j with rfl | hjpos
When $j = 0$, the sum simplifies to $\binom{2d - 1}{d - 1}$.
Since $d \ge 1$, we have $d - 1 < d - 0 = d$, so $\min(d - 0, d - 1) = d - 1$. Replacing the upper limit by $d - 1$ and applying `sum_ballot_weight_eq` with $a = d - 1$ (noting $d - 1 \le d - 1$ by `le_rfl`) evaluates the sum to $\binom{2d - 1}{d - 1}$.
uses
sum_ballot_weight_eq,le_rfl· have hmin : min (d - 0) (d - 1) = d - 1 := by omega rw [hmin, sum_ballot_weight_eq d (d - 1) le_rfl]
$\binom{2d - 1}{d - 1} = \binom{2d - 1}{d - 0}$, completing the $j = 0$ case.
Because $d \ge 1$, we have $d \le 2d - 1$. The symmetry identity for binomial coefficients (`Nat.choose_symm`) gives $\binom{2d - 1}{(2d - 1) - d} = \binom{2d - 1}{d}$. Since $(2d - 1) - d = d - 1$ and $d - 0 = d$ by `Nat.sub_zero`, this shows that the left-hand value $\binom{2d - 1}{d - 1}$ equals the target $\binom{2d - 1}{d - 0}$.
uses
Nat.choose_symm,Nat.sub_zerohave hsymm := Nat.choose_symm (by omega : d ≤ 2 * d - 1) have : 2 * d - 1 - d = d - 1 := by omega rw [this] at hsymm rw [Nat.sub_zero, ← hsymm]
When $j > 0$, the sum evaluates directly to $\binom{2d - 1}{d - j}$.
Because $j \ge 1$, we have $d - j \le d - 1$, which makes $\min(d - j, d - 1) = d - j$. Rewriting the minimum to $d - j$ and applying the summation identity `sum_ballot_weight_eq` for $a = d - j$ yields the right-hand side $\binom{2d - 1}{d - j}$.
uses
sum_ballot_weight_eq· have hmin : min (d - j) (d - 1) = d - j := by omega rw [hmin, sum_ballot_weight_eq d (d - j) (by omega)]
Nat.eq_zero_or_pos- A natural number is either 0 or strictly positive: $n = 0 \lor n > 0$.
sum_ballot_weight_eq- For $a \le d - 1$, the sum of ballot weights $\sum_{s=0}^a \text{ballot\_weight}(2d - 1, s)$ equals $\binom{2d - 1}{a}$.
le_rfl- Reflexivity of $\le$: $a \le a$ for any element in a preorder.
Nat.choose_symm- Symmetry of binomial coefficients: if $k \le n$, then $\binom{n}{n - k} = \binom{n}{k}$.
Nat.sub_zero- Subtracting zero from a natural number leaves it unchanged: $n - 0 = n$.
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.
/-- Sum of ballot weights up to min(d - j, d - 1) equals (2d - 1).choose (d - j). -/theorem sum_ballot_weight_min_eq (d j : ℕ) (hd : 1 ≤ d) (hj : j ≤ d) : ∑ s ∈ Finset.range (min (d - j) (d - 1) + 1), ballot_weight (2 * d - 1) s = (2 * d - 1).choose (d - j) := by rcases Nat.eq_zero_or_pos j with rfl | hjpos · have hmin : min (d - 0) (d - 1) = d - 1 := by omega rw [hmin, sum_ballot_weight_eq d (d - 1) le_rfl] have hsymm := Nat.choose_symm (by omega : d ≤ 2 * d - 1) have : 2 * d - 1 - d = d - 1 := by omega rw [this] at hsymm rw [Nat.sub_zero, ← hsymm] · have hmin : min (d - j) (d - 1) = d - j := by omega rw [hmin, sum_ballot_weight_eq d (d - j) (by omega)]