VC dimension of the class of polynomial classifiers of degree $n$

Question

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 classification problem with the instance domain being $X = \mathbb R$.

For every $n \in \mathbb N$ let $H_n$ be the class of polynomial classifiers of degree $n$; namely, $H_n$ is the set of all classifiers 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$.

Answer 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$.