I'm stuck on this combinatorics question:
Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$.
I've managed to prove it for the case when $n$ is even (by using Sperner's lemma, assuming for contradiction that $\large\binom{n}{k} < \binom{n}{\left\lfloor\frac{n}2\right\rfloor}$ and getting a contradiction with $k \le \frac{n}{2}$, but I don't think this will work for $n$ odd, and I haven't yet used the fact that every $A \in F$ has $|A| \le k$.
I feel like the pidgeon hole principle will come into play, but I can't quite see how.
Any help would be greatly appreciated, thanks!
You can prove it by double induction on $k$ and $n\ge 2k$. For all $k$, Sperner’s theorem gives you the result for $n=2k$. Now suppose that the result is true whenever $k<k_0$ and $n\ge 2k$ and whenever $k=k_0$ and $2k_0\le n\le n_0$, and suppose that $\mathscr{F}$ is an antichain in $\wp([n_0+1])$ such that $|A|\le k_0$ for every $A\in\mathscr{F}$. Let $$\mathscr{F}_0=\{A\in\mathscr{F}:n_0+1\notin A\}$$ and $$\mathscr{F}_1=\{A\setminus\{n_0+1\}:n_0+1\in A\in\mathscr{F}\}\;.$$ Then $\mathscr{F}_0$ is an antichain in $\wp([n_0])$ such that $|A|\le k_0$ for each $A\in\mathscr{F}_0$, $\mathscr{F}_1$ is an antichain in $\wp([n_0])$ such that $|A|\le k_0-1$ for all $A\in\mathscr{F}_1$, and $|\mathscr{F}|=|\mathscr{F}_0|+|\mathscr{F}_1|$. Now apply the induction hypothesis and the identity $$\binom{n_0+1}{k_0}=\binom{n_0}{k_0}+\binom{n_0}{k_0-1}\;.$$