Proof of Theorem 17, p. 18 — key identity Σ_{s′=s}^{k} T(i,s′) = Σ_j C(n−i,j)(1/j)∏_{ℓ≤j}(k−s+ℓ)∏_{t=i}^{n−j−1}(s+t)
ProvedSecretaryAdvice.SamplesDual.key_identitybinomial-coefficientsclosed-formcombinatorial-identityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be natural numbers, and , and let be the quantity of the proof of Theorem 17 (p. 17). Then
By the reduction step of the proof, this identity is exactly what is needed to establish the inductive step of Theorem 17 (with the maximum ignored).
Formalization Note The empty-product convention for is used (the term has an empty product over ).
Preamble
import Mathlib import Definitions.Def_SecretaryAdvice_SamplesDual_ClosedForm open Finset
Formal statement
namespace SecretaryAdvice.SamplesDual
/-- Proof of Theorem 17, p. 18: for `1 ≤ i < n` and `0 ≤ s ≤ k`,
`Σ_{s'=s}^{k} T(i,s') = Σ_{j=1}^{n−i} C(n−i,j) · (1/j) · ∏_{ℓ=1}^{j} (k−s+ℓ) · ∏_{t=i}^{n−j−1} (s+t)`. -/
theorem key_identity (n k i s : ℕ) (hi : 1 ≤ i) (hin : i < n) (hs : s ≤ k) :
∑ s' ∈ Icc s k, T n k i s' = keyRHS n k i s := by sorry
end SecretaryAdvice.SamplesDual
Source
Dütting et al., Secretaries with Advice, arXiv:2011.06726v1, p. 18, proof of Theorem 17 ("to establish the claim it suffices to show that")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.