Lemma 3.2: Φ_d(m) = ∑_{i=0}^{d} (m choose i)
ProvedComputationalLearning.phi_closed_formcombinatoricsvc-dimension
Lemma 3.2. .
Formally: for all natural numbers , the function of Definition 11 equals .
Preamble
import Definitions.Def_ComputationalLearning_VC open MeasureTheory
Formal statement
namespace ComputationalLearning
/-- **Lemma 3.2** (p. 56): `Φ_d(m) = ∑_{i=0}^{d} (m choose i)`. -/
theorem phi_closed_form (d m : ℕ) :
Phi d m = ∑ i ∈ Finset.range (d + 1), m.choose i := by sorry
end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §3.4 p. 56, Lemma 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.