monotone_distribution_telescoping_sum
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- mixture_representation_monotone_distributionLet $P : \mathbb{N}^+ \to \mathbb{R}$ be a nonincreasing probability distribution on the positive integers, so that $P(k) \ge 0$ for all…
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).
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).
uses
dif_posclassical 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
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).
uses
monotoneMixtureWeight,ne_of_gthave 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]
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).
uses
Finset.sum_bij,Finset.mem_Icc,PNat.coe_le_coe,PNat.coe_inj.mp,lt_of_lt_of_le,Finset.mem_Icc.mprhave 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]
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`.
uses
PNat.coe_le_coehave hleNat : (n : ℕ) ≤ (N : ℕ) := (PNat.coe_le_coe n N).mpr hleThe 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).
uses
Finset.sum_congr,Pi.neg_apply,Finset.sum_Icc_subcalc ∑ 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).
- While on paper the sum ∑ k = n to N of (P(k) - P(k+1)) telescopes directly to P(n) - P(N+1), Mathlib's library lemma for telescoping sums on intervals (`Finset.sum_Icc_sub`) is stated for functions on ℕ rather than ℕ+. The formal proof therefore explicitly defines an extension f : ℕ → ℝ and verifies a bijection between the intervals in ℕ+ and ℕ.
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 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]