AFTD Auto-Formalizing Theoretical Domains

binomial_convolution_restricted_weights

theoremverifiedformalization

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}$.

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

    line 5

    uses sum_range_sum_range_swap

      rw [sum_range_sum_range_swap d hd (ballot_weight (2 * d - 1)) (fun j => (n - (2 * d - 1)).choose j)]
  2. 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}$.

    lines 6–11

    uses Finset.mem_range, sum_ballot_weight_min_eq, Nat.lt_succ_iff.mp

      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)]
  3. 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.

    line 12

    uses Finset.sum_congr

      rw [Finset.sum_congr rfl h_inner]
  4. 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$.

    line 13

    uses sum_choose_convolution

      exact 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

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