For n= 1 (and for n= 2,3 also) the result is easily checked, so assume the result is true for k up to n-1 and prove for k = n.
Now, let $\displaystyle 1\le m\le \frac{m(m+1)}{2}$:
1) If $\displaystyle m\le \frac{(m-1)m}{2}$ then apply the inductive hypothesis to the subset $\displaystyle N:=\{1,2,...,n-1\}\subset\{1,2,...,n\}=\mathbb{S}$, otherwise;
2) $\displaystyle k\in \left\{\frac{n(n-1)}{2}+1,\frac{(n-1)n}{2}+2,\ldots,\frac{(n-1)n}{2}+n=\frac{n(n+1)}{2}\right\}$ , and then it's easy to see that $\displaystyle k=1+2+\ldots+(n-1)+k$ , with $\displaystyle 1\le k\le n$
Tonio