Max size of set that doesn't contain k+1 length chain

56 Views Asked by At

Let's take the set $G$ which is the set of all the subsets of the set $\{1,2,3,\ldots n\}$. $A,B$ that belongs $G$ are incomparable if $A \not\subseteq B$ and $B \not\subseteq A$. We know the notion of chain that all elements in a chain are comparable.

We need to find the maximum size of the subset $X$ of $G$ such that there doesn't exist a $k+1$ length chain in the $X$. This means among any $k+1$ elements that we took from $X$ there exists $2$ elements which are incomparable. We need to prove that size of the set $X$ is atmost $$|X| \le \sum_{i=\frac{n-k+1}{2}}^{\frac{n+k-1}{2}} {n \choose i}$$

I am able to prove that for a 2 length chain, but how to do it for a $k+1$ length chain?