The limit of a sum: $\lim_{n\to \infty} \sum_{k=1}^{n} \left(\frac{k}{n^2}-\frac{k^2}{n^3}\right)$

Evaluate the following limit: $$\lim_{n\to \infty} \sum_{k=1}^{n} \left(\frac{k}{n^2}-\frac{k^2}{n^3}\right)$$

I haven't ever taken the limit of the sum... Where do I start?

Do I start taking the sum?

• "Riemann sum" is the keyword you are looking for. – Clement C. Nov 17 '17 at 21:52
• Factor out $\frac{1}{n}$ and you got this :) – Dionel Jaime Nov 17 '17 at 21:53

With Riemann sums:

We have $$\sum_{k=1}^n \left(\frac{k}{n^2}-\frac{k^2}{n^3}\right) = \frac{1}{n}\sum_{k=1}^n \left(\frac{k}{n}-\left(\frac{k}{n}\right)^2\right) = \frac{1}{n}\sum_{k=1}^n \frac{k}{n}\left(1-\frac{k}{n}\right)$$ which is a Riemann sum for $f\colon[0,1]\to\mathbb{R}$ defined by $f(x)=x(1-x)$. Therefore, we have $$\lim_{n\to\infty} \sum_{k=1}^n \left(\frac{k}{n^2}-\frac{k^2}{n^3}\right) = \int_0^1 f(x)dx = \left[\frac{x^2}{2}-\frac{x^3}{3}\right]^1_0 =\boxed{ \frac{1}{6}}\,.$$

Without Riemann sums:

Here, you can directly use the facts that $\sum_{k=1}^n k = \frac{n(n+1)}{2}$ and $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$ to compute the sum, and conclude afterwards. $$\sum_{k=1}^n \left(\frac{k}{n^2}-\frac{k^2}{n^3}\right) = \frac{1}{n^2}\sum_{k=1}^n k-\frac{1}{n^3}\sum_{k=1}^n k^2 = \frac{n(n+1)}{2n^2}-\frac{n(n+1)(2n+1)}{6n^3} \xrightarrow[n\to\infty]{} \frac{1}{2} - \frac{1}{3} = \boxed{\frac{1}{6}}\,.$$

Extra approach: by convolutions. By defining, for any $n\in\mathbb{N}$, $$a_n = \sum_{k=0}^{n}k(n-k)$$ we have that $a_n$ is the coefficient of $x^n$ in $\left(0+1x+2x^2+3x^3+\ldots\right)^2$, i.e. $$a_n = [x^n]\left(\frac{x}{(1-x)^2}\right)^2 = [x^{n-2}]\frac{1}{(1-x)^4}\stackrel{\text{stars and bars}}{=}[x^{n-2}]\sum_{k\geq 0}\binom{k+3}{3}x^k$$ so $a_n = \binom{n+1}{3}$ and $$\lim_{n\to +\infty}\frac{a_n}{n^3} = \frac{1}{3!}=\color{red}{\frac{1}{6}}.$$

• Nice! (Not as convoluted as I thought reading the first line.) – Clement C. Nov 17 '17 at 22:16
• Is "stars and bars" a reference to binomial theorem? If there is some humor I am not aware of I want to be enlightened. +1 for your answer – Paramanand Singh Nov 18 '17 at 2:40
• @ParamanandSingh: no humor, it is the classical combinatorial lemma known as such: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) – Jack D'Aurizio Nov 18 '17 at 2:42
• Ok i knew the technique, but not the name "stars and bars". :) – Paramanand Singh Nov 18 '17 at 2:43

Since Riemann sums seem to do the trick, let's look at $d(u) =\lim_{n\to \infty} \sum_{k=1}^{n} \frac{k^u}{n^{u+1}}$ where $u \ge 0$.

Doing what was done before,

$\begin{array}\\ d(u) &=\lim_{n\to \infty} \dfrac1{n}\sum_{k=1}^{n} \frac{k^u}{n^{u}}\\ &=\lim_{n\to \infty} \dfrac1{n}\sum_{k=1}^{n} \left(\frac{k}{n}\right)^u\\ &=\int_0^1 x^u dx\\ &=\dfrac1{u+1}\\ \end{array}$

Therefore, if $d(u, v) =\lim_{n\to \infty} \sum_{k=1}^{n} \left(\frac{k^u}{n^{u+1}}-\frac{k^v}{n^{v+1}}\right)$, $d(u, v) =\dfrac1{u+1}-\dfrac1{v+1}$.

If $u=1, v=2$, this gives $d(1, 2) =\dfrac12-\dfrac13 =\dfrac16$.

• In the RHS of d(u,v), two of the u's ought to be v's. – Clement C. Nov 18 '17 at 0:46
• Thanks. Fixed and upvoted. The perils of copy and paste. – marty cohen Nov 18 '17 at 1:01