Evaluating $\lim\limits_{n\to\infty} \sum_{k=1}^{n^2} \frac{n}{n^2+k^2}$

How would you evaluate the following series?

$$\lim_{n\to\infty} \sum_{k=1}^{n^2} \frac{n}{n^2+k^2}$$

Thanks.

-
Maple says $\pi/2$ –  i. m. soloveichik Sep 4 '12 at 14:20
It looks like you might be able to interpret the summand as a Riemann sum ... –  Michael Joyce Sep 4 '12 at 14:31
@ Michael Joyce: Yeah. That's true. Anyway, I'm interested in more approaching ways if possible. –  Chris's sis Sep 4 '12 at 14:31

Recall that for any decreasing function $f:\mathbb{R}\to\mathbb{R}$ and any $N>1$ we have $$\int\limits_1^{N+1}f(x)dx\leq \sum\limits_{k=1}^{N}f(k)\leq \int\limits_0^N f(x)dx$$ After substitutions $N=n^2$, $f(x)=n/(n^2+x^2)$ and simple computations we have $$\arctan\frac{n^2+1}{n}-\arctan \frac{1}{n}\leq\sum\limits_{k=1}^{n^2}\frac{n}{n^2+k^2}\leq\arctan n$$ Lets take a limit $n\to\infty$, then from sandwich lemma it follows $$\lim\limits_{n\to\infty}\sum\limits_{k=1}^{n^2}\frac{n}{n^2+k^2}=\frac{\pi}{2}$$

P.S. First solution was not rigor enough.

-
The first approach is unconventional and seems to require some further analysis since there is no Riemann sum in the picture, stricto sensu. –  Did Sep 4 '12 at 17:43
@Norbert: the second approach seems the way to go. –  Chris's sis Sep 4 '12 at 17:55
In fact, @did is right as regards the first approach. –  Chris's sis Sep 4 '12 at 17:56
+1 from me Sir! (^ₒ^) –  Anastasiya-Romanova 秀 May 21 '14 at 12:57
How is the decreasing function property called? –  REr Nov 11 '14 at 17:51

Hint: $$\int_0^a f(x) dx \approx \sum_{k=0}^{na} \frac{1}{n}f\left(\frac{k}{n}\right)$$ Use $f(x) = \frac{1}{1+x^2}$.

Addendum: Fortunately, $f(x)$ is strictly decreasing, therefore the error is bounded by $\frac{f(0)-f(a)}n$, which again is $<\frac1n$, independent of $a$. This last observation allows us to use $a=n$ without spoiling convergence to $\int_0^\infty f(x) dx$.

-
With $a=n$, the approach becomes unconventional and seems to require some further analysis. –  Did Sep 4 '12 at 17:42
@did: I believe you're right. I've tried to add the necessary analysis to my answer. –  robjohn Sep 5 '12 at 12:46

Using $x=k/n$ and $\mathrm{d}x=1/n$ $$S_m(n)=\sum_{k=0}^{mn}\frac{n}{n^2+k^2}=\sum_{k=0}^{mn}\frac{1}{1+(k/n)^2}\frac1{\vphantom{k^2}n}\tag{1}$$ is a Riemann Sum for $$I_m=\int_0^m\frac{\mathrm{d}x}{1+x^2}\tag{2}$$ For any $m$ and $n$, we have $$\sum_{k>mn}\frac{n}{n^2+k^2}\le\sum_{k>mn}\frac{n}{k(k-1)}=\frac1m\tag{3}$$ which implies that $$S_m(n)\le S_\infty(n)=\lim_{m\to\infty}S_m(n)\le S_m(n)+\frac1m\tag{4}$$ Since $$I_\infty=\lim\limits_{m\to\infty}I_m=\int_0^\infty\frac{\mathrm{d}x}{1+x^2}\tag{5}$$ for any $\epsilon>0$, there is an $m_\epsilon\ge\frac1{\large\epsilon}$ so that for $m\ge m_\epsilon$, $$I_\infty-\epsilon\le I_m=\lim_{n\to\infty}S_m(n)\le I_\infty\tag{6}$$ Finally, there is an $n_\epsilon\ge m_\epsilon$ so that for $n\ge n_\epsilon$, $$I_\infty-2\epsilon\le S_{m_\epsilon}(n)\le I_\infty+\epsilon\tag{7}$$ Since $m_\epsilon\ge\frac1{\large\epsilon}$, $(4)$ and $(7)$ yield that for $n\ge n_\epsilon$ $$I_\infty-3\epsilon\le S_n(n)\le I_\infty+2\epsilon\tag{8}$$ Since $\epsilon$ was arbitrary, we get that $$\lim_{n\to\infty}S_n(n)=I_\infty\tag{9}$$ which translates to $$\lim_{n\to\infty}\sum_{k=0}^{n^2}\frac{n}{n^2+k^2}=\int_0^\infty\frac{\mathrm{d}x}{1+x^2}=\frac\pi2\tag{10}$$

-
Nice and detailed (+1) –  Chris's sis Sep 5 '12 at 12:54
@Chris'sister: This looks deceptively like a reference to Riemann Sums, but since the upper index is $n^2$, we have to handle the improper integral carefully. –  robjohn Sep 5 '12 at 13:01
@ robjohn: Right. And this is because m is not fixed, but it tends to $\infty$. –  Chris's sis Sep 5 '12 at 13:03

Here's another approach.

First, note that $$\begin{eqnarray*} \sum_{k=n^2+1}^\infty \frac{n}{n^2+k^2} &<& \sum_{k=n^2+1}^\infty \frac{n}{k^2} \\ &\le& n\int_{n^2}^\infty \frac{dx}{x^2} \\ &=& \frac{1}{n}. \end{eqnarray*}$$ We also need the partial fraction expansion of $\coth x$, $$\begin{eqnarray*} \coth x &=& \lim_{N\to\infty} \sum_{k=-N}^N \frac{1}{x-i k \pi} \\ &=& \frac{1}{x} + \sum_{k=1}^\infty \frac{2x}{x^2+k^2\pi^2}. \end{eqnarray*}$$ Then we find $$\begin{eqnarray*} \lim_{n\to\infty} \sum_{k=1}^{n^2} \frac{n}{n^2+k^2} &=& \lim_{n\to\infty}\left( \sum_{k=1}^\infty \frac{n}{n^2+k^2} - \sum_{k=n^2+1}^\infty \frac{n}{n^2+k^2} \right) \\ &=& \lim_{n\to\infty} \sum_{k=1}^\infty \frac{n}{n^2+k^2} \\ &=& \lim_{n\to\infty} \left(\frac{\pi}{2}\coth n\pi - \frac{1}{2n}\right) \\ &=& \frac{\pi}{2}. \end{eqnarray*}$$

-
@Chris'sister: Sometimes life gets in the way! Aigner and Ziegler have a nice derivation of the partial fraction expansion for $\cot x$ in Proofs from The Book (see Cotangent and the Herglotz trick). I tend to think of such sums in terms of complex analysis. –  user26872 Sep 6 '12 at 16:43
yeah, nice! Thanks for the link. –  Chris's sis Sep 6 '12 at 17:00


\begin{align} \color{#c00000}{\sum_{k = 1}^{n^{2}}{n \over n^{2} + k^{2}}}&= -\Im\sum_{k = 1}^{n^{2}}{1 \over k + \ic n} =-\Im\sum_{k = 0}^{n^{2} - 1}{1 \over k + 1 + \ic n} \\[3mm]&=-\Im\sum_{k = 0}^{\infty}\pars{% {1 \over k + 1 + \ic n} - {1 \over k + n^{2} + 1 + \ic n}} \\[3mm]&=-n^{2}\,\Im\sum_{k = 0}^{\infty} {1 \over \pars{k + n^{2} + 1 + \ic n}\pars{k + 1 + \ic n}} \\[3mm]&=\color{#c00000}{% \Im\bracks{\Psi\pars{1 + \ic n} - \Psi\pars{n^{2} + 1 + \ic n}}} \end{align} where $\ds{\Psi\pars{z}}$ is the Digamma Function. $\ds{z \in {\mathbb C}\verb=\=\braces{0,-1,-2,\ldots}}$. We'll use the property $\ds{\Psi\pars{z} \approx \ln\pars{z}}$ when $\ds{\verts{z} \gg 1}$ and $\ds{\verts{{\rm Arg}\pars{z}} < \pi}$.

Then, \begin{align}\color{#00f}{\large% \lim_{n \to \infty}\sum_{k = 1}^{n^{2}}{n \over n^{2} + k^{2}}}&= \lim_{n \to \infty}\Im\bracks{\Psi\pars{1 + \ic n} - \Psi\pars{n^{2} + 1 + \ic n}} \\[3mm]&=\lim_{n \to \infty} \Im\bracks{\ln\pars{1 + \ic n} - \ln\pars{n^{2} + 1 + \ic n}} \\[3mm]&= \lim_{n \to \infty}\bracks{\arctan\pars{n} - \arctan\pars{n \over n^{2} + 1}} =\color{#00f}{\large{\pi \over 2}} \end{align}

-