MHB Can You Tackle the Subset Chain Challenge in Math?

[Euge]

Here is this week's POTW:

-----
Let $X$ be a nonempty set of $n$ elements. Suppose $\emptyset \neq S_0 \subset S_1 \subset S_2\subset \cdots$ be a chain of subsets of $X$. Prove that to every positive integer $k \ge 2\log n$, there corresponds an index $j\in \{1,\ldots, k\}$ such that $$\operatorname{card}(S_j - S_{j-1}) \le \frac{2\operatorname{card}(S_{j-1})}{k}\log n$$

[Note: The logarithm here is the natural logarithm.]
-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[Euge]

No one answered this week's problem. You can read my solution below.

Spoiler

If the result does not hold, then there exists an integer $k \ge 2\log n$ such that for all indices $j \in \{1,\ldots, k\}$, $$\operatorname{card}(S_j - S_{j-1}) > \frac{2\operatorname{card}(S_{j-1}}{k}\log n$$ Since $\operatorname{card}(S_j - S_{j-1}) = \operatorname{card}(S_j) - \operatorname{card}(S_{j-1})$, equivalently $$\operatorname{card}(S_j) > \left(1 + \frac{2}{k}\log n\right)\operatorname{card}(S_{j-1})$$ By the inequality $1 + 2x \ge e^x$ for all $x\in [0,1]$, it follows that for every $j$, $\operatorname{card}(S_j) > n^{1/k} \operatorname{card}(S_{j-1})$. Inductively, $\operatorname{card}(S_j) > n^{j/k}\operatorname{card}(S_0) \ge n^{j/k}$ for all $j$. In particular $\operatorname{card}(S_k) > n$, a contradiction.