monotoneMixtureWeight_sum_by_parts
For any sequence $P : \mathbb{N}^+ \to \mathbb{R}$ and any $n \in \mathbb{N}^+, the finite sum of mixture weights satisfies $\sum_{k=1}^n w_k = \sum_{k=1}^n P(k) - n P(n+1)$.
Statement
lemma monotoneMixtureWeight_sum_by_parts (P : ℕ+ → ℝ) (n : ℕ+) :
∑ k ∈ Finset.Iic n, monotoneMixtureWeight P k =
(∑ k ∈ Finset.Iic n, P k) - (n : ℝ) * P (n + 1)- Source
- arXiv:2610.01563 Lemma 3 (1) 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 every function $P : \mathbb{N}^+ \to \mathbb{R}$ and every positive integer $n \in \mathbb{N}^+$, the sum over all positive integers $k \le n$ of $\mathrm{monotoneMixtureWeight}(P, k)$ is equal to $\left(\sum_{k \in \mathbb{N}^+, k \le n} P(k)\right) - n \cdot 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 theorem is proved by induction on $n \in \mathbb{N}^+$. In the base case $n = 1$, the index range is the singleton $\{1\}$, and the identity reduces to the definition $w_1 = P(1) - P(2)$. In the inductive step, separating the final term at $n + 1$ from both sums allows applying the induction hypothesis to the sum up to $n$; the additional weight $(n+1)(P(n+1) - P(n+2))$ then telescopes with $-n P(n+1)$ into $P(n+1) - (n+1)P(n+2)$.
The identity holds for the base case $n = 1$.
We proceed by induction on $n \in \mathbb{N}^+$ using `PNat.recOn`. In the base case $n = 1$, since $1$ is the bottom element $\bot$ of $\mathbb{N}^+$, the initial interval $\{k \le 1\}$ equals the singleton $\{1\}$ by `Finset.Iic_bot`. Applying `Finset.sum_singleton` reduces the sum on each side to its single term at $k = 1$. Unfolding the definition of `monotoneMixtureWeight` gives $1 \cdot (P(1) - P(2))$ on the left and $P(1) - 1 \cdot P(2)$ on the right, which are equal by ring arithmetic.
uses
PNat.recOn,Finset.Iic_bot,Finset.sum_singletoninduction n using PNat.recOn with | one => have h1 : Finset.Iic (1 : ℕ+) = {1} := by have : (1 : ℕ+) = ⊥ := rfl rw [this, Finset.Iic_bot] rw [h1, Finset.sum_singleton, Finset.sum_singleton] unfold monotoneMixtureWeight push_cast ring
If the identity holds for $n$, then it holds for $n + 1$.
For the inductive step, we separate the $(n + 1)$-th term from the sum up to $n + 1$ on both sides using `Finset.sum_Iic_add_zero`, and replace the sum up to $n$ on the left by the induction hypothesis (ih). Unfolding `monotoneMixtureWeight` at $n + 1$ yields $(n + 1)(P(n + 1) - P(n + 2))$. Expanding the products gives $-n P(n + 1) + (n + 1) P(n + 1) = P(n + 1)$, so the terms telescope and both sides simplify to the same polynomial expression, closed by ring arithmetic.
uses
Finset.sum_Iic_add_zero| succ n ih => rw [Finset.sum_Iic_add_zero, Finset.sum_Iic_add_zero, ih] unfold monotoneMixtureWeight push_cast ring
PNat.recOn- The induction principle for positive integers $\mathbb{N}^+$: if a property holds for $1$ and is preserved by the successor step $n \mapsto n + 1$, it holds for all positive integers.
Finset.Iic_bot- In a partially ordered type with a bottom element $\bot$, the initial interval of elements $\le \bot$ is the singleton $\{\bot\}$.
Finset.sum_singleton- The sum of a function over a singleton set $\{a\}$ is the value of the function at $a$.
Finset.sum_Iic_add_zero- The sum of a function over the interval of elements $\le a + 1$ equals the sum over the interval $\le a$ plus the term at $a + 1$.
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.
/-- Summation by parts for finite sums of mixture weights. -/lemma monotoneMixtureWeight_sum_by_parts (P : ℕ+ → ℝ) (n : ℕ+) : ∑ k ∈ Finset.Iic n, monotoneMixtureWeight P k = (∑ k ∈ Finset.Iic n, P k) - (n : ℝ) * P (n + 1) := by induction n using PNat.recOn with | one => have h1 : Finset.Iic (1 : ℕ+) = {1} := by have : (1 : ℕ+) = ⊥ := rfl rw [this, Finset.Iic_bot] rw [h1, Finset.sum_singleton, Finset.sum_singleton] unfold monotoneMixtureWeight push_cast ring | succ n ih => rw [Finset.sum_Iic_add_zero, Finset.sum_Iic_add_zero, ih] unfold monotoneMixtureWeight push_cast ring