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 < \dots < 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{aligned} 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{aligned}$$
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 $\varepsilon > 0$ the set that contains $s_k = \frac{1}{2}(k + \varepsilon)(k + \varepsilon - 1)$ satisfies the stated criterion.

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 < \dots < 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{aligned} 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{aligned}$$
as required.