binomial_convolution_restricted_weights
For natural numbers $d$ and $n$ with $1 \le d$ and $2d - 1 \le n$, the double sum $\sum_{s \in \text{range } d} \text{ballot\_weight}(2d - 1, s) \sum_{j \in \text{range}(d - s + 1)} \binom{n - (2d - 1)}{j}$ equals $\binom{n}{d}$.
Statement
theorem binomial_convolution_restricted_weights (d n : ℕ) (hd : 1 ≤ d) (hn : 2 * d - 1 ≤ n) :
∑ s ∈ Finset.range d, ballot_weight (2 * d - 1) s *
(∑ j ∈ Finset.range (d - s + 1), (n - (2 * d - 1)).choose j) = n.choose d- Formalizes
- arXiv:2611.06860 "Largest Sperner families with bounded VC-dimension", Lemma 2.5
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- ballot_weightThe function ballot_weight taking two natural numbers $p$ and $k$ and returning the natural number defined as: if $k = 0$ then…
- sum_range_sum_range_swapFor any positive integer $d$ and functions $f, g : ℕ → ℕ$, the summation identity…
- sum_ballot_weight_min_eqFor natural numbers $d$ and $j$ with $1 \le d$ and $j \le d$, the sum…
- sum_choose_convolutionFor natural numbers $d$ and $n$ with $2d - 1 \le n$, the binomial sum $\sum_{j=0}^d \binom{n - (2d-1)}{j} \binom{2d-1}{d-j}$ equals…
Read back from the Lean
For all natural numbers $d$ and $n$, assuming $1 \le d$ and $2d - 1 \le n$, the sum over $s \in \{0, \dots, d - 1\}$ of $\text{ballot\_weight}(2d - 1, s) \times \sum_{j=0}^{d - s} \binom{n - (2d - 1)}{j}$ equals $\binom{n}{d}$, where $\text{ballot\_weight}(p, k)$ is defined as $\binom{p}{0}$ when $k = 0$, and $\binom{p}{k} - \binom{p}{k - 1}$ otherwise.
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 evaluates the double sum by first swapping the order of summation. The new inner sum over the ballot weights telescopes to the single binomial coefficient $\binom{2d - 1}{d - j}$ for each $j \le d$. Finally, the outer sum simplifies via the Chu–Vandermonde convolution to $\binom{n}{d}$.
The double sum is rewritten by interchanging the summation order to $\sum_{j=0}^d \binom{n - (2d - 1)}{j} \sum_{s=0}^{\min(d - j, d - 1)} \text{ballot\_weight}(2d - 1, s)$.
By `sum_range_sum_range_swap`, the triangular summation domain $0 \le s < d$ and $0 \le j \le d - s$ can be re-indexed by letting $j$ range from $0$ to $d$ while $s$ ranges from $0$ to $\min(d - j, d - 1)$.
uses
sum_range_sum_range_swaprw [sum_range_sum_range_swap d hd (ballot_weight (2 * d - 1)) (fun j => (n - (2 * d - 1)).choose j)]
For each $j \in \{0, \dots, d\}$, the inner sum over $s$ evaluates to $\binom{2d - 1}{d - j}$, making the summand $\binom{n - (2d - 1)}{j} \binom{2d - 1}{d - j}$.
For any index $j$ in the range $\{0, \dots, d\}$, we have $j < d + 1$ (by `Finset.mem_range`), so $j \le d$ (by `Nat.lt_succ_iff.mp`). Lemma `sum_ballot_weight_min_eq` then shows that the inner sum of ballot weights telescopes to $\binom{2d - 1}{d - j}$.
uses
Finset.mem_range,sum_ballot_weight_min_eq,Nat.lt_succ_iff.mphave h_inner : ∀ j ∈ Finset.range (d + 1), (n - (2 * d - 1)).choose j * (∑ s ∈ Finset.range (min (d - j) (d - 1) + 1), ballot_weight (2 * d - 1) s) = (n - (2 * d - 1)).choose j * (2 * d - 1).choose (d - j) := by intro j hj rw [Finset.mem_range] at hj rw [sum_ballot_weight_min_eq d j hd (Nat.lt_succ_iff.mp hj)]
The full summation simplifies to $\sum_{j=0}^d \binom{n - (2d - 1)}{j} \binom{2d - 1}{d - j}$.
Congruence of finite sums (`Finset.sum_congr`) replaces each inner sum with the simplified binomial coefficient proved in the previous step.
uses
Finset.sum_congrrw [Finset.sum_congr rfl h_inner]
The remaining sum equals $\binom{n}{d}$.
The identity `sum_choose_convolution` applies the Chu–Vandermonde convolution to sum over all pairs of indices summing to $d$, giving $\binom{n}{d}$ since $2d - 1 \le n$.
uses
sum_choose_convolutionexact sum_choose_convolution d n hn
Finset.mem_range- An index $m$ belongs to the range of $n$ if and only if $m < n$.
Finset.sum_congr- Two finite sums are equal if their index sets are identical and their summands agree on every element of that set.
Nat.lt_succ_iff.mp- If $m < k + 1$ for natural numbers, then $m \le k$.
sum_ballot_weight_min_eq- For $1 \le d$ and $j \le d$, the partial sum $\sum_{s=0}^{\min(d - j, d - 1)} \text{ballot\_weight}(2d - 1, s)$ equals $\binom{2d - 1}{d - j}$.
sum_choose_convolution- For natural numbers $d$ and $n$ with $2d - 1 \le n$, the Chu–Vandermonde convolution $\sum_{j=0}^d \binom{n - (2d - 1)}{j} \binom{2d - 1}{d - j}$ equals $\binom{n}{d}$.
sum_range_sum_range_swap- For $1 \le d$, the double sum $\sum_{s=0}^{d-1} f(s) \sum_{j=0}^{d - s} g(j)$ equals the swapped double sum $\sum_{j=0}^d g(j) \sum_{s=0}^{\min(d - j, d - 1)} f(s)$.
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.
/-- Binomial convolution identity for restricted weights in terms of double sums of binomial coefficients. -/theorem binomial_convolution_restricted_weights (d n : ℕ) (hd : 1 ≤ d) (hn : 2 * d - 1 ≤ n) : ∑ s ∈ Finset.range d, ballot_weight (2 * d - 1) s * (∑ j ∈ Finset.range (d - s + 1), (n - (2 * d - 1)).choose j) = n.choose d := by rw [sum_range_sum_range_swap d hd (ballot_weight (2 * d - 1)) (fun j => (n - (2 * d - 1)).choose j)] have h_inner : ∀ j ∈ Finset.range (d + 1), (n - (2 * d - 1)).choose j * (∑ s ∈ Finset.range (min (d - j) (d - 1) + 1), ballot_weight (2 * d - 1) s) = (n - (2 * d - 1)).choose j * (2 * d - 1).choose (d - j) := by intro j hj rw [Finset.mem_range] at hj rw [sum_ballot_weight_min_eq d j hd (Nat.lt_succ_iff.mp hj)] rw [Finset.sum_congr rfl h_inner] exact sum_choose_convolution d n hn