VC dimension of polynomials (in one variable) of degree d Linear functions in one variable have VC dimension =3 and I remember reading somewhere that the VC for polynomials of degree $d$ is $(d^2 + 3d + 2)/2$.

I am searching for ideas that can prove the above claim (and perhaps generalize to many variables as well, though that seems too much to hope for).

Any approach, even an incomplete one, will be appreciated.

To define the problem properly: Given a plane (2D, x and y coordinates) what is the size of maximum set that can be shattered if you can use classifying functions that are polynomial ($y=p(x)$) of degree at mode $d$, and you are free to choose which side of the curve you want to label positive. 

For example, label (x,y) as positive iff $y &gt; x^2 +5x +9$.
The basic method works like this: Assume your inequalities are of the form 

$$ \sum_{i \le d} a_i x^i \le 0$$

Then you construct a lifting map to a space of higher dimension in which each monomial corresponds to one dimension. Now the polynomial can be expressed as a linear combination of the new dimensions and you can invoke the usual result for half spaces in the resulting space. 

I'm not sure where you get your bound from: the correct expression for the VC dimension of polynomials in d variables of degree D is $\binom{d + D}{d}$, which is the number of monomials of degree at most D formed from d variables.