= Solution
If $x_{1:n}$ is shattered by $\bigcup_{k=1}^r\mathcal F_k$, then all $2^n$ label vectors belong to the union of the label-vector sets generated by the individual classes. The <shattering coefficient of a union> and the <Sauer-Shelah lemma> therefore give
$$
2^n
\leq\sum_{k=1}^rs(\mathcal F_k,n)
\leq r\sum_{j=0}^v\binom nj
\leq\boxed{r(n+1)^v}.
$$
Taking base-two logarithms yields
$$
n\leq\log_2r+v\log_2(n+1).
$$
For $r>1$, apply the stated elementary bound with $\alpha=\log_2r$ and $\beta=v\geq3$:
$$
n\leq4v\log_2(2v)+2\log_2r.
$$
If $r=1$, the assertion follows directly from $n\leq v$. Taking the largest shattered sample size proves
$$
\boxed{
\operatorname{VC}\left(\bigcup_{k=1}^r\mathcal F_k\right)
\leq4v\log_2(2v)+2\log_2r
}.
$$
Back to article page
