Lemma 29.5: if VCdim(H_bin) = d then every set shattered by the One-versus-All class H^{OvA,k}_bin has size ≤ 3kd log(kd)

Lemma 29.5. If $d = \operatorname{VCdim}(H_{bin})$ then $\operatorname{Ndim}(H^{OvA,k}_{bin}) \le 3kd\log(kd)$.

Formally: every set shattered by $H^{OvA,k}_{bin}$ has size at most $3kd\log(kd)$ (natural logarithm; the bound is $0$ when $kd \le 1$). The book's step $|(H_{bin})_C| \le |C|^d$ fails for small $|C|$ (for $|C| = 2$, $d = 1$), but the statement is true: the exact Sauer count $2^c \le (\sum_{i \le d}\binom{c}{i})^k$ gives it for every $(k, d)$ except $(2, 1)$ and $(3, 1)$. In those two cases, group a shattered set by the label pair $\{f_0(x), f_1(x)\}$. On pairs $\{0, b\}$ the realized sets are $h_b \setminus h_0$, and on pairs $\{a, b\}$ with $a \ge 1$ they are $h_a$ itself. The class $\{B \setminus A : A, B \in H_{bin}\}$ cannot shatter $5$ points: on them $|H_{bin}| \le 6$, and the $6$ pairs $A = B$ all give $\emptyset$, so at most $31 < 32$ sets. Hence $|C| \le 4 < 4.16$ for $k = 2$ and $|C| \le 4 + 4 + 1 = 9 < 9.89$ for $k = 3$.