AFTD Auto-Formalizing Theoretical Domains

monotoneMixtureWeight_sum_by_parts

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

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

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

    lines 5–13

    uses PNat.recOn, Finset.Iic_bot, Finset.sum_singleton

      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
  2. 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.

    lines 14–18

    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

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