p. 36 — Σ_{t<T} √(Σ_{i<t} 1/(T−i−1)²) ≤ 2√T + √2
ProvedResolvingNRM.FRUpper.sqrt_sum_boundinequalityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
For every integer ,
This is the analytic step of the proof of Proposition 3 that turns the per-period bounds of Lemma 8 into the total: the -th summand is of order , and these sum to order .
Formalization Note. For and the denominator is at least , so no division by zero occurs. An empty inner sum (at ) is .
Preamble
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_FRUpper_Model open RLPBidPrice.Unbiased Matrix
Formal statement
namespace ResolvingNRM.FRUpper
/-- The summation chain of App. C.2, p. 36:
`∑_{t=0}^{T-1} √(∑_{i=0}^{t-1} 1 / (T − i − 1)²) ≤ 2√T + √2` for every integer `T ≥ 1`. -/
theorem sqrt_sum_bound (T : ℕ) (hT : 1 ≤ T) :
∑ t ∈ Finset.range T, Real.sqrt (∑ i ∈ Finset.range t, 1 / ((T : ℝ) - i - 1) ^ 2)
≤ 2 * Real.sqrt T + Real.sqrt 2 := by sorry
end ResolvingNRM.FRUpper
Source
Bumpensanti, Wang, A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management, arXiv:1802.06192v3, App. C.2, chain of inequalities at the top of p. 36
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.