I am trying to show $\sum_{k = 1} ^n \frac{(k - 1)n^2}{n(n - k + 1)^2} = O(n^2)$. This should be easy enough, but I am stuck and can't see how to finish it off.
My solution so far: This is the same as showing $\sum_{k = 1}^n \frac{(k - 1)}{n(n - k + 1)^2} \leq C$ for some $C > 0$ when $n$ is sufficiently large. Hence \begin{align*} \sum_{k = 1}^n \frac{(k - 1)}{n(n - k + 1)^2} &= \sum_{j = 1} ^{n - 1} \frac{j}{n(n - j)^2} \\ &= \sum_{j = 1} ^{n - 1} \frac{j}{n(j - n)^2} \\ &= \sum_{j = 1} ^{n - 1} \frac{j}{n(j^2 - 2jn + n^2)} \\ &= \sum_{j = 1} ^{n - 1} \frac{1}{n(j - 2n + \frac{n^2}{j})}. \end{align*} Now the last term resembles $\sum_{j = 1} ^n \frac{1}{j}$ the harmonic series, which is $O(\log n)$. How could I incorporate this fact with the calculation? Or am I thinking in the wrong direction here?
You are on the right track: note that by letting $i=n-j$ we find $$\sum_{j = 1} ^{n - 1} \frac{j}{n(n-j)^2}=\frac{1}{n}\sum_{i = 1} ^{n - 1} \frac{n-i}{i^2}=\sum_{i = 1} ^{n - 1} \frac{1}{i^2}- \frac{1}{n}\sum_{i = 1} ^{n - 1} \frac{1}{i}=O(1)+\frac{O(\ln(n))}{n}=O(1).$$