Eq. (3.17) —
ProvedScenarioApproach.Removal.choose_le_powcombinatoricsp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1scenario-approach
For all natural numbers and ,
This elementary estimate controls the combinatorial factor in the bound (3.13) of Theorem 3.9 and is used in the derivation of the explicit violation level of Theorem 1.2.
Formalization Note The equality is stated in (factorials cast to reals) and the inequality in , with . The hypothesis makes the natural-number subtractions and exact.
Preamble
import Mathlib
Formal statement
namespace ScenarioApproach.Removal
theorem choose_le_pow (k d : ℕ) (hd : 1 ≤ d) :
((k + d - 1).choose k : ℝ) =
((k + d - 1).factorial : ℝ) / ((k.factorial : ℝ) * ((d - 1).factorial : ℝ)) ∧
(k + d - 1).choose k ≤ (k + d - 1) ^ (d - 1) := by sorry
end ScenarioApproach.Removal
Source
Campi & Garatti, Introduction to the Scenario Approach, SIAM/MOS 2018, DOI 10.1137/1.9781611975444, p. 48, Eq. (3.17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.