IRL_ABooklet_2023

Solution 1. Proof by induction on $n$. The condition holds trivially if $n=1$, so let us assume it holds for some $n\ge 1$ and prove it for $n+1$. Write the elements of the set $S$ of $n+1$ elements as $$s_1<s_2<\cdots <s_{n-1}<s_n<s_{n+1}.$$ From the condition in the question, and the inductive hypothesis: $$s_{n+1}\ge s_n+\sqrt{s_n+s_{n+1}}>\frac{1}{2}n(n-1)+\sqrt{\frac{1}{2}n(n-1)+s_{n+1}}.$$ Multiplying by 2, rearranging and squaring, we have: $$(2s_{n+1}-n(n-1){)}^2>2n(n-1)+4s_{n+1}.$$ Collecting like terms gives: $$\begin{array}{rl}0<& 4s_{n+1}^2-4n(n-1)s_{n+1}+n^2(n-1{)}^2-2n(n-1)-4s_{n+1}\\ =& 4s_{n+1}^2-2(2n^2-2n+2)s_{n+1}+n(n-1)(n+1)(n-2)\\ =& (2s_{n+1}-n(n+1))(2s_{n+1}-(n-1)(n-2)).\end{array}$$ Now the term in the second pair of large brackets is positive, as: $$2s_{n+1}>2s_n>n(n-1)\ge (n-2)(n-1).$$ Therefore the first term is also positive, which implies $s_{n+1}>\frac{1}{2}n(n+1)$, completing the inductive step.

Remark. This result is best possible, given that for $\epsilon >0$ the set that contains $s_k=\frac{1}{2}(k+\epsilon )(k+\epsilon -1)$ satisfies the stated criterion.

---

Alternative solution.

Solution 2. Before we prove the statement by induction, we prove a lemma. Lemma. If $x<y$ are positive real numbers satisfying $y-x\ge \sqrt{x+y}$, then $$y\ge \frac{1}{2}(2x+1+\sqrt{8x+1}).$$ Proof. Because $y-x>0$, the inequality $y-x\ge \sqrt{x+y}$ is equivalent to $(y-x{)}^2\ge x+y$. This can be rearranged into $y^2-(2x+1)y+(x^2-x)\ge 0$. We keep the positive real number $x$ fixed and consider $$f(y)=y^2-(2x+1)y+(x^2-x).$$ The roots of this polynomial are $$y_{\pm }=\frac{1}{2}\left(2x+1\pm \sqrt{8x+1}\right).$$

Since the leading coefficient of $f(y)$ is positive, we have $f(y)\ge 0$ if and only if $y\le y_{-}$ or $y\ge y_{+}$. By Vieta, $y_{-}{y}_{+}=x^2-x<x^2$ and so it is not possible that $y_{-}$ and $y_{+}$ are both greater or equal than $x$, hence $y_{-}<x$. Therefore, if $x<y$ and $f(y)\ge 0$, we have $y\ge y_{+}$, as claimed. $\square$ To start the inductive proof of the statement of the problem, we let the elements of the set $S$ be $x_1<x_2<\cdots <x_{n-1}<x_n<x_{n+1}$. By assumption we have $x_1>0$ which settles the case $n=1$. For the inductive step, we suppose $x_n>\frac{1}{2}n(n-1)$. This implies $8x_n+1>4n^2-4n+1=(2n-1{)}^2$. We wish to prove $x_{n+1}>\frac{1}{2}n(n+1)$. Applying the lemma with $y=x_{n+1}$ and $x=x_n$, we obtain $$\begin{array}{rl}{x}_{n+1}& \ge \frac{1}{2}(2x_n+1+\sqrt{8x_n+1})\\ & >\frac{1}{2}(n(n-1)+1+(2n-1))=\frac{1}{2}n(n+1),\end{array}$$ as required.