, 2016

We show that $S(nk) < S(n) + S(k)$. Cancel the summand of $S(k)$ on both sides of this inequality, then add $\frac{1}{2}$ to both sides and rearrange. This yields the equivalent inequality
$$\frac{1}{k+1} + \frac{1}{k+2} + \dots + \frac{1}{nk} + \frac{1}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}. \quad (*)$$
Divide the first $(n-1)k$ numbers on the left hand side into $n-1$ sums of $k$ fractions with consecutive denominators: $A_1 = \frac{1}{k+1} + \dots + \frac{1}{2k}$, $A_2 = \frac{1}{2k+1} + \dots + \frac{1}{3k}$, ..., $A_{n-1} = \frac{1}{(n-1)k+1} + \dots + \frac{1}{nk}$.
Then compare $A_j$ with $\frac{1}{j}$ for $j=1, \dots, n-1$. Denoting $d_j = \frac{1}{j} - A_j = \frac{1}{j} - \frac{1}{jk+1} - \frac{1}{jk+2} - \dots - \frac{1}{jk+k}$
we have
$$d_j = \left( \frac{1}{jk} - \frac{1}{jk+1} \right) + \left( \frac{1}{jk} - \frac{1}{jk+2} \right) + \dots + \left( \frac{1}{jk} - \frac{1}{jk+k} \right) =$$
$$= \frac{1}{jk(jk+1)} + \frac{2}{jk(jk+2)} + \dots + \frac{k}{jk(jk+k)} >$$

$$> \frac{1+2+...+k}{jk(jk+k)} = \frac{k+1}{2k} \cdot \frac{1}{j(j+1)} > \frac{1}{2j} - \frac{1}{2(j+1)}$$
It follows that
$$\left(1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}\right)-\left(\frac{1}{k+1}+\frac{1}{k+2}+\dots+\frac{1}{nk}\right)=d_1+\dots+d_{n-1}+\frac{1}{n} > \left(\frac{1}{2}-\frac{1}{4}\right)+\left(\frac{1}{4}-\frac{1}{6}\right)+\dots+\left(\frac{1}{2n-2}-\frac{1}{2n}\right)+\frac{1}{n} = \frac{1}{2}+\frac{1}{2n} > \frac{1}{2}$$
This proves (*), hence $S(nk) < S(n) + S(k)$ holds true.