Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Riemann-sum bound: 1c∑k=I+1cΨ(k/c)≤1c+∫(I+1)/c1Ψ\frac1c\sum_{k=I+1}^{c}\Psi(k/c)\le\frac1c+\int_{(I+1)/c}^1\Psic1​∑k=I+1c​Ψ(k/c)≤c1​+∫(I+1)/c1​Ψ

Proved
PersonalizedAssortment.IB.riemann_sum_bound

by mikedeng1 · Oct 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1penalty-functionreal-analysisriemann-sums

Let Ψ\PsiΨ be a penalty function (Ψ:[0,1]→[0,1]\Psi:[0,1]\to[0,1]Ψ:[0,1]→[0,1] increasing, Ψ(0)=0\Psi(0)=0Ψ(0)=0, Ψ(1)=1\Psi(1)=1Ψ(1)=1). Let ccc be a positive integer and III an integer with 0≤I<c0\le I<c0≤I<c. Then

1c∑k=I+1cΨ ⁣(kc)  ≤  1c+∫(I+1)/c1Ψ(y) dy.\frac1c\sum_{k=I+1}^{c}\Psi\!\left(\frac kc\right)\;\le\;\frac1c+\int_{(I+1)/c}^{1}\Psi(y)\,dy .c1​k=I+1∑c​Ψ(ck​)≤c1​+∫(I+1)/c1​Ψ(y)dy.

In the proof of Theorem 1, III is the final inventory IiTI_i^TIiT​ of a product with initial inventory c=cic=c_ic=ci​. The bound turns the discrete dual value of that product into the continuous expression that appears in αcmin⁡(Ψ)\alpha_{c_{\min}}(\Psi)αcmin​​(Ψ).

Preamble
import Mathlib
import Definitions.Def_PersonalizedAssortment_IB_PenaltyFunction
Formal statement
namespace PersonalizedAssortment.IB

/-- §A.3, p. 1549: for a penalty function `Ψ`, a positive integer `c` and an integer `0 ≤ I < c`,
`(1/c) ∑_{k=I+1}^{c} Ψ(k/c) ≤ 1/c + ∫_{(I+1)/c}^1 Ψ(y) dy`. -/
theorem riemann_sum_bound (Ψ : ℝ → ℝ) (hΨ : IsPenaltyFunction Ψ) (c : ℕ) (hc : 0 < c)
    (I : ℕ) (hI : I < c) :
    1 / (c : ℝ) * ∑ k ∈ Finset.Ioc I c, Ψ ((k : ℝ) / (c : ℝ)) ≤
      1 / (c : ℝ) + ∫ y in ((I : ℝ) + 1) / (c : ℝ)..1, Ψ y := by sorry

end PersonalizedAssortment.IB
Source
Golrezaei, Nazerzadeh, Rusmevichientong, Real-Time Optimization of Personalized Assortments, Management Sci. 60(6), 2014, https://doi.org/10.1287/mnsc.2014.1939, p. 1549, Section A.3, proof of Theorem 1, display after 'Because Psi(1) = 1 and Psi is increasing, we have'
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let Ψ:R→R\Psi : \mathbb R \to \mathbb RΨ:R→R satisfy:

  • Ψ\PsiΨ maps [0,1][0,1][0,1] into [0,1][0,1][0,1];
  • Ψ\PsiΨ is nondecreasing on [0,1][0,1][0,1];
  • Ψ(0)=0\Psi(0)=0Ψ(0)=0 and Ψ(1)=1\Psi(1)=1Ψ(1)=1.

No concavity, continuity or differentiability is assumed. Let ccc be a natural number with c>0c > 0c>0, and let III be a natural number with I<cI < cI<c. The statement asserts

1c∑k=I+1cΨ ⁣(kc)  ≤  1c+∫(I+1)/c1Ψ(y) dy,\frac1c \sum_{k = I+1}^{c} \Psi\!\left(\frac kc\right) \;\le\; \frac1c + \int_{(I+1)/c}^{1} \Psi(y)\,dy,c1​k=I+1∑c​Ψ(ck​)≤c1​+∫(I+1)/c1​Ψ(y)dy,

where kkk runs over the integers I+1,I+2,…,cI+1, I+2, \dots, cI+1,I+2,…,c.

Degenerate cases.

  • Since 1≤I+1≤c1 \le I + 1 \le c1≤I+1≤c, the lower limit (I+1)/c(I+1)/c(I+1)/c lies in (0,1](0, 1](0,1], and every point k/ck/ck/c in the sum lies in (0,1](0,1](0,1].
  • If I=c−1I = c - 1I=c−1, the sum has the single term Ψ(1)=1\Psi(1) = 1Ψ(1)=1 and the integral is over [1,1][1,1][1,1]. The claim then reads 1c≤1c\frac1c \le \frac1cc1​≤c1​.
  • If c=1c = 1c=1, the hypotheses force I=0I = 0I=0, which is the same case.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 21, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me