Proving Sauer-Shelah's theorum I've been working on some problems in introductory combinatorics, and I would
like some help on going about proving Sauer-Shelah's theorem.
A family $\mathcal{F}$ shatters a set $A$ if for every $B \subset A$, there is
an $F \in \mathcal{F}$ such that $F \cap A = B.$ I want to show that if
$\mathcal{F} \subset 2^{[n]}$ (i.e. the power set of $[n]$) and
$|\mathcal{F}| > \sum_{i=0}^k \binom{n}{i}$, then there is a set $A \subset
[n]$ of size $k+1$ such that $\mathcal{F}$ shatters $A$.
I started this by going about an "assume for the sake of contradiction" proof in
which I stated that for all sets $A \subset [n]$ of size $k+1$, $\mathcal{F}$
does not shatter $A$. Thus, for every $A$ that satisfies the above, there
exists a $B \subset A$ such that there is no $F \in \mathcal{F}$ such that
$F \cap A = B.$ The problem is, I am having some difficulty figuring out how
the construction of $\mathcal{F}$ makes meaningful implications about the
contents of $B$ in this situation. Is it possible that I should go about this
proof directly? Any recommendations would be appreciated.
 A: The induction proof is easier if you prove a stronger result: if $\mathscr{F}\subseteq 2^{[n]}$, then $\mathscr{F}$ shatters at least $|\mathscr{F}|$ subsets of $[n]$. Since $[n]$ has only $\sum_{i=0}^k\binom{n}i$ subsets of cardinality less than $k+1$, any $\mathscr{F}$ of cardinality greater than $\sum_{i=0}^k\binom{n}i$ must then shatter some subset of cardinality at least $k+1$ and hence one of cardinality $k+1$.
Clearly every non-empty $\mathscr{F}$ shatters $\varnothing$, so in particular $\mathscr{F}$ shatters at least one subset of $[n]$ if $|\mathscr{F}|=1$. Now assume that $|\mathscr{F}|>1$, and $\mathscr{G}$ shatters at least $|\mathscr{G}|$ subsets for each $\mathscr{G}\subsetneqq\mathscr{F}$. For each $r\in[n]$ let $\mathscr{F}_r=\{F\in\mathscr{F}:r\in F\}$ and $\mathscr{F}_r'=\mathscr{F}\setminus\mathscr{F}_r$.


*

*Show that there is an $r\in[n]$ such that $\mathscr{F}_r\ne\varnothing\ne\mathscr{F}_r'$.


By hypothesis $\mathscr{F}_r$ and $\mathscr{F}_r'$ shatter at least $|\mathscr{F}_r|$ and $|\mathscr{F}_r'|$ subsets, respectively. Let $\mathscr{S}$ be the family of subsets shattered by $\mathscr{F}$, $\mathscr{S}_r$ be the family of subsets shattered by $\mathscr{F}_r$ and $\mathscr{S}_r'$ the family of subsets shattered by $\mathscr{F}_r'$.


*

*Show that $$\mathscr{S}\supseteq(\mathscr{S}_r\setminus\mathscr{S}_r')\cup(\mathscr{S}_r'\setminus\mathscr{S}_r)\cup(\mathscr{S}_r\cap\mathscr{S}_r')\cup\{A\cup\{r\}:A\in\mathscr{S}_r\cap\mathscr{S}_r'\}\;,$$ and that the four sets whose union is being taken on the right are pairwise disjoint.  

*Conclude that $|\mathscr{S}|\ge|\mathscr{F}|$.

