VC dimension of the class of polynomial classifiers of degree $n$ I came across this statement on page 85 of the book "understanding machine learning: from theory to algorithms"

The general idea is as follows:

Consider a binary classiﬁcation problem with the instance domain being $X = \mathbb R$. 

For every $n \in \mathbb N$ let $H_n$ be the class of polynomial classiﬁers of degree $n$; namely, $H_n$ is the set of all classiﬁers of the form $h(x) = \operatorname{sign}(p(x))$, where $p\colon  \mathbb R \to \mathbb R$ is a polynomial of degree $n$.

Prove that the VC dimension of $H_n$ is $n+1$.
The idea is that a polynomial of degree $n$ has at most $n$ roots, and so can change signs at most $n$ times. Therefore no polynomial of degree $n$ can form an alternating pattern +-+-... or -+-+... of length $n+2$. This shows that the VC dimension is at most $n+1$.

On the other hand, for any set of $n+1$ pairs $(x_1,y_1),\ldots,(x_{n+1},y_{n+1})$, there is a polynomial of degree $n$ which interpolates them, given by the Lagrange interpolation formula. Using $y_i = \pm 1$, you can easily show that any set of $n+1$ points is shattered. Therefore the VC dimension is exactly $n+1$.