Proof of Theorem 17, pp. 17–18 — two forms of T(i,s′)
ProvedSecretaryAdvice.SamplesDual.t_formsbinomial-coefficientsclosed-formcombinatorial-identityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be natural numbers, and , and let be the quantity defined in the proof of Theorem 17 (p. 17),
Then
The second form collapses the double sum over and into a single sum over ; it is the form in which the base case and the inductive step of the key identity are carried out.
Preamble
import Mathlib import Definitions.Def_SecretaryAdvice_SamplesDual_ClosedForm open Finset
Formal statement
namespace SecretaryAdvice.SamplesDual
/-- Proof of Theorem 17, pp. 17–18: the first and the last displayed expressions of `T(i,s')`
agree:
`T(i,s') = (n−i) ∏_{t=i+1}^{n−1} (s'+t)
− Σ_{j=1}^{n−i−1} (n−i) · C(n−i−1,j) · 1/(j(j+1)) · ∏_{ℓ=1}^{j} (k−s'+ℓ) · ∏_{t=i+1}^{n−j−1} (s'+t)`. -/
theorem t_forms (n k i s' : ℕ) (hi : 1 ≤ i) (hin : i < n) (hs : s' ≤ k) :
T n k i s' =
((n : ℝ) - i) * (∏ t ∈ Icc (i + 1) (n - 1), ((s' : ℝ) + t)) -
∑ j ∈ Icc 1 (n - i - 1),
((n : ℝ) - i) * ((n - i - 1).choose j : ℝ) * (1 / ((j : ℝ) * ((j : ℝ) + 1))) *
(∏ ℓ ∈ Icc 1 j, ((k : ℝ) - s' + ℓ)) *
(∏ t ∈ Icc (i + 1) (n - j - 1), ((s' : ℝ) + t)) := by sorry
end SecretaryAdvice.SamplesDual
Source
Dütting et al., Secretaries with Advice, arXiv:2011.06726v1, pp. 17–18, proof of Theorem 17, the three displayed expressions of T(i, s′) (first = last)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.