Show that $f(n)=\sum_{k=1}^n \frac n {n^2+k^2}$ is strictly increasing

Question

I want to show that the function $f:\mathbb N \to \mathbb Q$ defined by$$f(n)=\sum_{k=1}^n \frac n {n^2+k^2}$$

is strictly increasing. Could I have a hint on how to go about this? I have tried playing around with $f(n+1)-f(n)$ but it's all so messy with the different denominators that I'm not sure what to do.

Answer 1

$$ \begin{align} &\sum_{k=1}^{n+1}\frac{n+1}{k^2+(n+1)^2}-\sum_{k=1}^n\frac{n}{k^2+n^2}\tag1\\ &=\frac1{2n+2}+\sum_{k=1}^n\left(\frac{n+1}{k^2+(n+1)^2}-\frac{n}{k^2+n^2}\right)\tag2\\ &=\frac1{2n+2}-\sum_{k=1}^n\frac{n(n+1)-k^2}{\left(k^2+(n+1)^2\right)\left(k^2+n^2\right)}\tag3\\ &=\frac1{2n+2}-\frac1{n(n+1)}\sum_{k=1}^n\frac{1-\frac{k^2}{n(n+1)}}{\left(1+\frac{k^2}{(n+1)^2}\right)\left(1+\frac{k^2}{n^2}\right)}\tag4\\ &\gt\frac1{2n+2}-\frac1{n(n+1)}\sum_{k=1}^n\frac{1-\frac{k(k-1)}{n^2}}{\left(1+\frac{k^2}{n^2}\right)\left(1+\frac{(k-1)^2}{n^2}\right)}\tag5\\ &=\frac1{2n+2}-\frac1{n+1}\sum_{k=1}^n\left[\frac{\frac{k}{n}}{1+\frac{k^2}{n^2}}-\frac{\frac{k-1}{n}}{1+\frac{(k-1)^2}{n^2}}\right]\tag6\\[9pt] &=0\tag7 \end{align} $$ Explanation:
$(2)$: separate the $k=n+1$ term from the left sum and combine the rest
$(3)$: algebra
$(4)$: algebra
$(5)$: $\frac{k}{n+1}\gt\frac{k-1}{n}$ and $\frac{1-xy}{\left(1+x^2\right)\left(1+y^2\right)}$ is strictly decreasing in $x$ when $x,y\in[0,1]$
$(6)$: algebra
$(7)$: telescoping series sums to $\frac12$

Answer 2

hint

Let $$f(x)=\frac{1}{1+x^2}$$

$f$ is strictly decreasing at $[0,1]$.

The sum $$\frac{1}{n}\sum_{k=1}^n\frac{1}{1+(\frac{k}{n})^2}$$ is a Darboux lower sum which increases when the step of the partage becomes smaller.

$$L(f,\sigma_n)<L(f,\sigma_{n+1})$$

Answer 3

A nice discussion of this problem is given in Monotonicity of Riemann Sums by D. Borwein, J. M. Borwein and B. Sims where conditions ensuring monotonicity of right and left Riemann sums are analysed.

• In particular according to Corollary 3 (Monotonicity for decreasing functions with a concave symmetrization) the following is valid:

  If the function $f:[0,1]\to \mathbb{R}$ is decreasing on the interval $[0,1]$ and its symmetrization \begin{align*} F_f(x)=\frac{1}{2}\left(f(x)+f(1-x)\right) \end{align*} is concave, then the right Riemann sum \begin{align*} \color{blue}{\tau_n(f)=\frac{1}{n}\sum_{k=1}^nf\left(\frac{k}{n}\right)} \end{align*} increases with $n$, necessarily to $\int_0^1f$.

• The following Example 2: Monotonicity of $\tau_n$ for $1/(1+x^2)$ is the current problem with \begin{align*} f(x)=\frac{1}{1+x^2} \end{align*} and \begin{align*} \color{blue}{\tau_n}&=\frac{1}{n}\sum_{k=1}^n\frac{1}{1+\left(\frac{k}{n}\right)^2}\color{blue}{=\sum_{k=1}^n\frac{n}{n^2+k^2}}\tag{1} \end{align*}

Since $f$ is decreasing in $[0,1]$ and the convexity of \begin{align*} F_f(x)&=\frac{1}{2}\left(f(x)+f(1-x)\right)\\ &=\frac{1}{2}\left(\frac{1}{1+x^2}+\frac{1}{1+(1-x)^2}\right) \end{align*} can be shown by checking the second derivative $F_f^{\prime\prime}(x)$ is negative in $[0,1]$, monotonicity of (1) follows according to Corollary 3.

Answer 4

I will supplement @Markus Scheuer's answer by providing a proof of the claim (Corollary 3 of Monotonicity of Riemann Sums by D. Borwein, J. M. Borwein and B. Sims) in a slightly generalized setting.

Lemma. Let $f : [0, 1] \to \mathbb{R}$ and $\lambda \in \mathbb{R}$. Suppose that $$F(x) = \lambda f(x) + (1-\lambda) f(1-x) $$ is concave. If we write $\tau_n = \sum_{k=1}^{n} f\left(\frac{k}{n}\right)\frac{1}{n}$, then we have the following inquality $$ \tau_{n+1} \geq \frac{1}{(n+1)^2}f(0) + \frac{n(n+2)}{(n+1)^2} \tau_n. \tag{*} $$

As a corollary, suppose that $f$ and $\lambda$ satisfy the assumption of Lemma. Then

• If $f(0)$ is the global maximum of $f$, then $\tau_{n+1} \geq \tau_n$ since $f(0) \geq \tau_n$.
• If $0$ is the unique maximum point of $f$, then we have strict inequality $\tau_{n+1} > \tau_n$.

---

Proof of Lemma. We may write

$$ \tau_{n+1} = \frac{f(1)}{n+1} + \sum_{k=1}^{n} F\left(\frac{k}{n+1}\right)\frac{1}{n+1}. $$

Now by using the identity $ \frac{k}{n+1} = \frac{k}{n+1}\left(\frac{k-1}{n}\right) + \frac{n+1-k}{n+1} \left( \frac{k}{n} \right) $ together with the concavity of $F$,

$$ F\left(\frac{k}{n+1}\right) \geq \frac{k}{n+1} F\left(\frac{k-1}{n}\right) + \frac{n+1-k}{n+1} F\left( \frac{k}{n} \right). $$

Plugging this back, we find that

\begin{align*} \tau_{n+1} &\geq \frac{f(1)}{n+1} + \sum_{k=1}^{n} \left[ \frac{k}{(n+1)^2} F\left(\frac{k-1}{n}\right) + \frac{n+1-k}{(n+1)^2} F\left( \frac{k}{n} \right) \right] \\ \\ % % &= \frac{f(1)}{n+1} + \color{red}{\lambda \sum_{k=1}^{n} \frac{k}{(n+1)^2} f\left(\frac{k-1}{n}\right)} + \color{blue}{(1-\lambda) \sum_{k=1}^{n} \frac{k}{(n+1)^2} f\left(\frac{n-k+1}{n}\right)} \\ &\hspace{4.1em} + \color{blue}{\lambda \sum_{k=1}^{n} \frac{n+1-k}{(n+1)^2} f\left( \frac{k}{n} \right)} + \color{red}{(1-\lambda) \sum_{k=1}^{n} \frac{n+1-k}{(n+1)^2} f\left( \frac{n-k}{n} \right)} \\ \\ % % &= \frac{f(1)}{n+1} + \color{red}{\lambda \sum_{k=0}^{n-1} \frac{k+1}{(n+1)^2} f\left(\frac{k}{n}\right)} + \color{blue}{(1-\lambda) \sum_{k=1}^{n} \frac{n+1-k}{(n+1)^2} f\left(\frac{k}{n}\right)} \\ &\hspace{4.1em} + \color{blue}{\lambda \sum_{k=1}^{n} \frac{n+1-k}{(n+1)^2} f\left( \frac{k}{n} \right)} + \color{red}{(1-\lambda) \sum_{k=0}^{n-1} \frac{k+1}{(n+1)^2} f\left( \frac{k}{n} \right)} \\ \\ % % &= \frac{f(0)}{(n+1)^2} + \color{red}{\sum_{k=0}^{n-1} \frac{k+1}{(n+1)^2} f\left(\frac{k}{n}\right)} + \color{blue}{\sum_{k=1}^{n} \frac{n+1-k}{(n+1)^2} f\left(\frac{k}{n}\right)} \\ \\ % % &= \frac{1}{(n+1)^2}f(0) + \frac{n(n+2)}{(n+1)^2} \tau_n \end{align*}

as desired. ////