5
$\begingroup$

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?

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

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}}\,. $$

$\endgroup$
5
$\begingroup$

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}}.$$

$\endgroup$
  • 2
    $\begingroup$ Nice! (Not as convoluted as I thought reading the first line.) $\endgroup$ – Clement C. Nov 17 '17 at 22:16
  • $\begingroup$ 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 $\endgroup$ – Paramanand Singh Nov 18 '17 at 2:40
  • $\begingroup$ @ParamanandSingh: no humor, it is the classical combinatorial lemma known as such: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) $\endgroup$ – Jack D'Aurizio Nov 18 '17 at 2:42
  • $\begingroup$ Ok i knew the technique, but not the name "stars and bars". :) $\endgroup$ – Paramanand Singh Nov 18 '17 at 2:43
2
$\begingroup$

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 $.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.