Proof of Theorem 17, p. 18 — base case s = k: T(i,k) = Σ_j C(n−i,j)(1/j) j! ∏_{t=i}^{n−j−1}(k+t)
ProvedSecretaryAdvice.SamplesDual.key_identity_basebinomial-coefficientscombinatorial-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
This is the key identity at (where ), the base of the backward induction over .
Preamble
import Mathlib import Definitions.Def_SecretaryAdvice_SamplesDual_ClosedForm open Finset
Formal statement
namespace SecretaryAdvice.SamplesDual
/-- Proof of Theorem 17, p. 18, base case `s = k` of the key identity:
`T(i,k) = Σ_{j=1}^{n−i} C(n−i,j) · (1/j) · j! · ∏_{t=i}^{n−j−1} (k+t)`. -/
theorem key_identity_base (n k i : ℕ) (hi : 1 ≤ i) (hin : i < n) :
T n k i k =
∑ j ∈ Icc 1 (n - i),
((n - i).choose j : ℝ) * (1 / (j : ℝ)) * (j.factorial : ℝ) *
(∏ t ∈ Icc i (n - j - 1), ((k : ℝ) + t)) := by sorry
end SecretaryAdvice.SamplesDual
Source
Dütting et al., Secretaries with Advice, arXiv:2011.06726v1, p. 18, proof of Theorem 17, base case s = k
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.