Appendix B, pp. 26–28 — inductive step: the key identity at s + 1 implies it at s
ProvedSecretaryAdvice.SamplesDual.key_identity_stepbinomial-coefficientscombinatorial-identityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be natural numbers, and , let be the quantity of the proof of Theorem 17, and write
If , then
Together with the base case this proves the key identity by backward induction over the signal .
Preamble
import Mathlib import Definitions.Def_SecretaryAdvice_SamplesDual_ClosedForm open Finset
Formal statement
namespace SecretaryAdvice.SamplesDual
/-- Appendix B, pp. 26–28, inductive step of the key identity: if it holds at `s + 1`, it holds
at `s` (for `1 ≤ i < n` and `0 ≤ s < k`). -/
theorem key_identity_step (n k i s : ℕ) (hi : 1 ≤ i) (hin : i < n) (hs : s < k)
(h : ∑ s' ∈ Icc (s + 1) k, T n k i s' = keyRHS n k i (s + 1)) :
∑ 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, pp. 26–28, Appendix B (Inductive Step in Proof of Theorem 17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.