Deal With These Sums Separately

Relevant wiki: Sum of n, n², or n³

Note: From the wiki above, we know that $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ . And we will applying this algebraic identity repeatedly throughout this solution.

$\begin{aligned} S_n & = \sum_{j=2}^n \sum_{k=1}^{j-1} \frac kj \\ & = \frac 12 + \frac 13 + \frac 23 + \frac 14 + \frac 24 + \frac 34+...+\frac 1n + \frac 2n +...+ \frac {n-1}n \\ & = \sum_{j=2}^n \frac {\sum_{k=1}^{j-1} k}j \\ & = \sum_{j=2}^n \frac {\frac {j(j-1)}2}j \\ & = \sum_{j=2}^n \frac {j-1}2 \\ & = \frac {(n-1)(2+n)}{2\cdot 2} - \frac {n-1}2 \end{aligned}$

$\begin{aligned} \implies S_{2016} & = \frac {2015 \cdot 2018}4 - \frac {2015}2 = \boxed{1015560} \end{aligned}$