3.4 Lower bound on growth function. Prove that Sauer's lemma (theorem 3.17) is tight, i.e., for any set X of m > d elements, show that there exists a hypothesis class H of VC-dimension d such that H(m) =

Pd i=0

????m i

.