AFTD Auto-Formalizing Theoretical Domains

monotone_distribution_telescoping_sum

theoremverified

For any sequence $P : \mathbb{N}^+ \to \mathbb{R}$ and any positive integers $n \le N$, the sum $\sum_{k=n}^N \frac{w_k}{k}$ telescopes to $P(n) - P(N+1)$.

Statement

lemma monotone_distribution_telescoping_sum (P : ℕ+ → ℝ) (n N : ℕ+) (hle : n ≤ N) :
    ∑ k ∈ Finset.Icc n N, monotoneMixtureWeight P k / (k : ℝ) =
      P n - P (N + 1)
Source
arXiv:2610.01563 Lemma 3 (2) proof
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • monotoneMixtureWeightFor a sequence $P : \mathbb{N}^+ \to \mathbb{R}$, the mixture weight at $k \in \mathbb{N}^+$ is defined by $w_k = k (P(k) - P(k+1))$.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

Read back from the Lean

For any function $P : \mathbb{N}^+ \to \mathbb{R}$ and any positive integers $n$ and $N$ such that $n \le N$, the sum over all positive integers $k$ in the closed interval $[n, N]$ of $\frac{\text{monotoneMixtureWeight}(P, k)}{k}$ equals $P(n) - P(N + 1)$.

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 sum by first canceling the factor of k in each term, reducing monotoneMixtureWeight(P, k) / k to P(k) - P(k+1). To apply Mathlib's telescoping sum theorem on intervals, the sequence P is extended to a function f on ℕ, and the sum is transferred from ℕ+ to ℕ via a canonical bijection. The sum on ℕ then telescopes to f(n) - f(N+1), which simplifies back to P(n) - P(N+1).

  1. An extension f : ℕ → ℝ of P to natural numbers satisfies f(k) = P(k) and f(k+1) = P(k+1) for all k ∈ ℕ+.

    We define f(m) to be P(m) whenever m > 0 (casting m to ℕ+) and 0 otherwise. For any positive integer k, k > 0 holds by definition, so the positive branch evaluates to P(k) via `dif_pos`. Likewise, k + 1 > 0, so f(k+1) reduces to P(k+1).

    lines 5–13

    uses dif_pos

      classical
      let f : ℕ → ℝ := fun m => if h : 0 < m then P ⟨m, h⟩ else 0
      have hf_coe (k : ℕ+) : f (k : ℕ) = P k := by
        dsimp [f]
        rw [dif_pos k.pos]
        congr 1
      have hf_succ (k : ℕ+) : f ((k : ℕ) + 1) = P (k + 1) := by
        dsimp [f]
        congr 1
  2. For every k ∈ [n, N], the summand monotoneMixtureWeight(P, k) / k simplifies to P(k) - P(k+1).

    Unfolding the definition `monotoneMixtureWeight` replaces the numerator with k * (P(k) - P(k+1)). Because k ∈ ℕ+, k > 0, which implies k ≠ 0 in ℝ (`ne_of_gt`). Canceling this non-zero factor of k from the numerator and denominator leaves P(k) - P(k+1).

    lines 14–20

    uses monotoneMixtureWeight, ne_of_gt

      have hterm : ∀ k ∈ Finset.Icc n N,
          monotoneMixtureWeight P k / (k : ℝ) = P k - P (k + 1) := by
        intro k hk
        rw [monotoneMixtureWeight]
        have hk0 : (k : ℝ) ≠ 0 := by
          exact_mod_cast (ne_of_gt k.pos)
        field_simp [hk0]
  3. The sum ∑ k = n to N of (P(k) - P(k+1)) over ℕ+ equals ∑ m = n to N of (f(m) - f(m+1)) over ℕ.

    We re-index the sum via `Finset.sum_bij` using the canonical coercion from ℕ+ to ℕ: 1. It maps [n, N] in ℕ+ into [n, N] in ℕ, since n ≤ k ≤ N implies (n : ℕ) ≤ (k : ℕ) ≤ (N : ℕ) by `PNat.coe_le_coe` and `Finset.mem_Icc`. 2. It is injective because coercion from ℕ+ to ℕ is injective (`PNat.coe_inj.mp`). 3. It is surjective: any m ∈ [n, N] in ℕ satisfies m ≥ n ≥ 1 > 0 (`lt_of_lt_of_le`), so m can be viewed as an element of ℕ+ belonging to [n, N] (`Finset.mem_Icc.mpr`, `PNat.coe_le_coe`). 4. At each index, the summands agree because f(k) = P(k) and f(k+1) = P(k+1).

    lines 21–37

    uses Finset.sum_bij, Finset.mem_Icc, PNat.coe_le_coe, PNat.coe_inj.mp, lt_of_lt_of_le, Finset.mem_Icc.mpr

      have hbij :
          ∑ k ∈ Finset.Icc n N, (P k - P (k + 1)) =
            ∑ m ∈ Finset.Icc (n : ℕ) (N : ℕ), (f m - f (m + 1)) := by
        refine Finset.sum_bij (fun k _ => (k : ℕ)) ?_ ?_ ?_ ?_
        · intro k hk
          rw [Finset.mem_Icc] at hk ⊢
          exact ⟨(PNat.coe_le_coe n k).mp hk.1, (PNat.coe_le_coe k N).mp hk.2⟩
        · intro a ha b hb hab
          exact PNat.coe_inj.mp hab
        · intro m hm
          rw [Finset.mem_Icc] at hm
          refine ⟨(⟨m, lt_of_lt_of_le n.pos hm.1⟩ : ℕ+), ?_, rfl⟩
          exact Finset.mem_Icc.mpr
            ⟨(PNat.coe_le_coe n (⟨m, lt_of_lt_of_le n.pos hm.1⟩ : ℕ+)).mp hm.1,
             (PNat.coe_le_coe (⟨m, lt_of_lt_of_le n.pos hm.1⟩ : ℕ+) N).mp hm.2⟩
        · intro k hk
          rw [hf_coe k, hf_succ k]
  4. The natural bounds satisfy (n : ℕ) ≤ (N : ℕ).

    The hypothesis n ≤ N in ℕ+ is converted to the natural number inequality (n : ℕ) ≤ (N : ℕ) via `PNat.coe_le_coe`.

    line 38

    uses PNat.coe_le_coe

      have hleNat : (n : ℕ) ≤ (N : ℕ) := (PNat.coe_le_coe n N).mpr hle
  5. The sum ∑ k = n to N of monotoneMixtureWeight(P, k) / k equals P(n) - P(N+1).

    A calculation chain evaluates the sum: 1. Replace each summand with P(k) - P(k+1) using `Finset.sum_congr` and the earlier simplification. 2. Transfer the sum from ℕ+ to ℕ using the bijection identity `hbij`. 3. Algebraically rewrite f(m) - f(m+1) as (-f)(m+1) - (-f)(m) using `Pi.neg_apply` and ring arithmetic. 4. Apply the standard telescoping lemma `Finset.sum_Icc_sub` on ℕ with (n : ℕ) ≤ (N : ℕ) to collapse the sum to (-f)(N+1) - (-f)(n). 5. Simplify (-f)(N+1) - (-f)(n) to f(n) - f(N+1) by `Pi.neg_apply` and ring arithmetic. 6. Convert f(n) and f(N+1) back to P(n) and P(N+1).

    lines 39–54

    uses Finset.sum_congr, Pi.neg_apply, Finset.sum_Icc_sub

      calc
        ∑ k ∈ Finset.Icc n N, monotoneMixtureWeight P k / (k : ℝ)
            = ∑ k ∈ Finset.Icc n N, (P k - P (k + 1)) := by
              exact Finset.sum_congr rfl hterm
        _ = ∑ m ∈ Finset.Icc (n : ℕ) (N : ℕ), (f m - f (m + 1)) := hbij
        _ = ∑ m ∈ Finset.Icc (n : ℕ) (N : ℕ), ((-f) (m + 1) - (-f) m) := by
              apply Finset.sum_congr rfl
              intro m hm
              simp only [Pi.neg_apply]
              ring
        _ = (-f) ((N : ℕ) + 1) - (-f) (n : ℕ) := by
              exact Finset.sum_Icc_sub hleNat (fun m => -f m)
        _ = f (n : ℕ) - f ((N : ℕ) + 1) := by
              simp only [Pi.neg_apply]
              ring
        _ = P n - P (N + 1) := by rw [hf_coe n, hf_succ N]
dif_pos
In a dependent if-then-else expression, if the condition is true, the expression reduces to the value of the 'then' branch.
monotoneMixtureWeight
The mixture weight definition: monotoneMixtureWeight(P, k) = k * (P(k) - P(k+1)).
ne_of_gt
If b < a in a preorder, then a ≠ b.
Finset.sum_bij
Two finite sums are equal if there is a bijection between their index sets that preserves summands.
Finset.mem_Icc
An element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.mem_Icc.mpr
If a ≤ x and x ≤ b, then x belongs to the closed interval [a, b].
PNat.coe_le_coe
For positive integers n and k, (n : ℕ) ≤ (k : ℕ) if and only if n ≤ k in ℕ+.
PNat.coe_inj.mp
If the natural number coercions of two positive integers are equal, the positive integers are equal.
lt_of_lt_of_le
If a < b and b ≤ c in a preorder, then a < c.
Finset.sum_congr
If two finite sets are equal and their summands agree on every element, their sums are equal.
Pi.neg_apply
The pointwise negation (-f)(x) is equal to -f(x).
Finset.sum_Icc_sub
For m ≤ n in ℕ, the sum ∑ i = m to n of (f(i+1) - f(i)) evaluates to f(n+1) - f(m).

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 w_k / k from n to N. -/lemma monotone_distribution_telescoping_sum (P : ℕ+ → ℝ) (n N : ℕ+) (hle : n ≤ N) :    ∑ k ∈ Finset.Icc n N, monotoneMixtureWeight P k / (k : ℝ) =      P n - P (N + 1) := by  classical  let f : ℕ → ℝ := fun m => if h : 0 < m then P ⟨m, h⟩ else 0  have hf_coe (k : ℕ+) : f (k : ℕ) = P k := by    dsimp [f]    rw [dif_pos k.pos]    congr 1  have hf_succ (k : ℕ+) : f ((k : ℕ) + 1) = P (k + 1) := by    dsimp [f]    congr 1  have hterm : ∀ k ∈ Finset.Icc n N,      monotoneMixtureWeight P k / (k : ℝ) = P k - P (k + 1) := by    intro k hk    rw [monotoneMixtureWeight]    have hk0 : (k : ℝ) ≠ 0 := by      exact_mod_cast (ne_of_gt k.pos)    field_simp [hk0]  have hbij :      ∑ k ∈ Finset.Icc n N, (P k - P (k + 1)) =        ∑ m ∈ Finset.Icc (n : ℕ) (N : ℕ), (f m - f (m + 1)) := by    refine Finset.sum_bij (fun k _ => (k : ℕ)) ?_ ?_ ?_ ?_    · intro k hk      rw [Finset.mem_Icc] at hk ⊢      exact ⟨(PNat.coe_le_coe n k).mp hk.1, (PNat.coe_le_coe k N).mp hk.2⟩    · intro a ha b hb hab      exact PNat.coe_inj.mp hab    · intro m hm      rw [Finset.mem_Icc] at hm      refine ⟨(⟨m, lt_of_lt_of_le n.pos hm.1⟩ : ℕ+), ?_, rfl⟩      exact Finset.mem_Icc.mpr        ⟨(PNat.coe_le_coe n (⟨m, lt_of_lt_of_le n.pos hm.1⟩ : ℕ+)).mp hm.1,         (PNat.coe_le_coe (⟨m, lt_of_lt_of_le n.pos hm.1⟩ : ℕ+) N).mp hm.2⟩    · intro k hk      rw [hf_coe k, hf_succ k]  have hleNat : (n : ℕ) ≤ (N : ℕ) := (PNat.coe_le_coe n N).mpr hle  calc    ∑ k ∈ Finset.Icc n N, monotoneMixtureWeight P k / (k : ℝ)        = ∑ k ∈ Finset.Icc n N, (P k - P (k + 1)) := by          exact Finset.sum_congr rfl hterm    _ = ∑ m ∈ Finset.Icc (n : ℕ) (N : ℕ), (f m - f (m + 1)) := hbij    _ = ∑ m ∈ Finset.Icc (n : ℕ) (N : ℕ), ((-f) (m + 1) - (-f) m) := by          apply Finset.sum_congr rfl          intro m hm          simp only [Pi.neg_apply]          ring    _ = (-f) ((N : ℕ) + 1) - (-f) (n : ℕ) := by          exact Finset.sum_Icc_sub hleNat (fun m => -f m)    _ = f (n : ℕ) - f ((N : ℕ) + 1) := by          simp only [Pi.neg_apply]          ring    _ = P n - P (N + 1) := by rw [hf_coe n, hf_succ N]
See it in the graphDiscuss this resultChallenge it