A second proof of Sauer–Shelah, from the multilinear polynomial space

Let $V$ be the vector space of all functions $\mathcal{F}\to \mathbb{R}$. For $A\subseteq [n]$, put $q_A(x):={\prod }_{i\in A}{x}_i{\prod }_{i\mathrm{\notin }A}(1-x_i)\mathrm{.}$ At an incidence vector $v_B$, this polynomial is $1$ when $B=A$ and $0$ otherwise. Therefore every $g\in V$ is represented on the incidence vectors of $\mathcal{F}$ by the multilinear polynomial ${\sum }_{A\in \mathcal{F}}g(A)q_A$, so the restrictions of all squarefree monomials $x_T$ span $V$.

If $\mid T\mid >d$, then $T$ is not shattered. Hence [L1] expresses the restriction of $x_T$ on $\mathcal{F}$ as a combination of the restrictions of the monomials $x_S$ with $S⊊T$. Inducting on $\mid T\mid$ shows that every monomial restriction is in the span of those with degree at most $d$.

Therefore the restrictions of the monomials $x_T$ with $\mid T\mid \le d$ already span $V$. Put $s:=\min \{d,n\}$; no subset of $[n]$ has size above $n$, so this is the same spanning family as the one with $\mid T\mid \le s$. By [L2], there are at most ${\sum }_{i=0}^s\left(\genfrac{}{}{0px}{}{n}{i}\right)$ of them. If $d\le n$ this is already ${\sum }_{i=0}^d\left(\genfrac{}{}{0px}{}{n}{i}\right)$; if $d>n$, then $\left(\genfrac{}{}{0px}{}{n}{i}\right)=0$ for $i>n$, so the same sum is also ${\sum }_{i=0}^d\left(\genfrac{}{}{0px}{}{n}{i}\right)$. Hence $\dim V=\mid \mathcal{F}\mid$ is at most ${\sum }_{i=0}^d\left(\genfrac{}{}{0px}{}{n}{i}\right)$. This is the same numerical bound as Sauer–Shelah: a family on $[n]$ of VC dimension at most $d$ has at most ${\sum }_{i=0}^d\left(\genfrac{}{}{0px}{}{n}{i}\right)$ members, proved by a genuinely different route.