Estonian Math Competitions

For any two subsets belonging to such a collection, the sets of the $k-1$ smallest elements must be different (or else they would be neighbours). There are $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ ways to choose the $k-1$ smallest elements, since the number $n$ cannot be one of them. Therefore $f(n,k)\le \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$, as desired.

---

Alternative solution.

For all $n\ge 2$ we have $f(n,1)=1$, since any two 1-element sets are neighbours. So for all $n\ge 2$ and $k=1$ the statement holds. We will prove the general statement by induction by $n$, taking the base case to be $n=2$. We will assume that the statement holds for $n-1$ and consider the $n$-element set $S=\{1,2,\dots ,n\}$. Let $1<k\le n-1$. The number of $k$-element subsets containing the number $n$ can be at most $f(n-1,k-1)$ in a neighbour-free collection, since removing the number $n$ from all of those subsets yields a neighbour-free collection of $k-1$-element subsets of $\{1,2,\dots ,n-1\}$. The number of $k$-element subsets not containing $n$ can be at most $f(n-1,k)$. Therefore $f(n,k)\le f(n-1,k-1)+f(n-1,k)$. By the induction assumption $f(n-1,k-1)\le \left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)$ and $f(n-1,k)\le \left(\genfrac{}{}{0ex}{}{n-2}{k-1}\right)$. Therefore by Pascal's rule $f(n,k)\le f(n-1,k-1)+f(n-1,k)\le \left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)+\left(\genfrac{}{}{0ex}{}{n-2}{k-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$, as desired.