Double Sum Challenge: Equate the Limit

[mathbalarka]

Equate the limit

$$\lim_{n \to \infty} \frac1{n} \sum_{i = 1}^n \sum_{j = 1}^n \frac1{i + j}$$

Note : This was a challenge from a user in mathstackexchange. From a glance, there should be many ways to do it, so partly I posed this problem to see how the resident analysts in MHB handle it. (although if you think this is solely an analytic problem, you're mistaken ;))

 

[chisigma]

Equate the limit

$$\lim_{n \to \infty} \frac1{n} \sum_{i = 1}^n \sum_{j = 1}^n \frac1{i + j}$$

[sp]The double series is equivalent to ...

$\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} \frac{1}{i + j} = \sum_{k=2}^{2 n} \frac{a_{k}}{k}\ (1)$

... where $a_{k}$ is the number of pair of i and j such that i + j = k. It is easy to see that...

$\displaystyle a_{k} = k-1\ \text{if}\ k<2 n, = 1,\ \text{if}\ k=2 n\ (2)$

... so that...

$\displaystyle \lim_{n \rightarrow \infty} \frac{1}{n}\ \sum_{i=1}^{n} \sum_{j=1}^{n} \frac{1}{i + j} = \lim_{n \rightarrow \infty} \frac{1}{n}\ \{ \sum_{k=2}^{2n -1} \frac{k-1}{k} + \frac{1}{2 n} \} = \displaystyle \lim_{n \rightarrow \infty} \frac{2 n - 3}{n} + \frac{1}{2 n^{2}} - \frac{1}{n}\ \sum_{k=2}^{2 n-1} \frac{1}{k} = 2\ (3)$ [/sp]

Kind regards

$\chi$ $\sigma$

 

[mathbalarka]

I am sorry, chisigma, but your solution is incorrect. You are on the right track, however. If you wish to check your solution and repost it, you're more than welcome.

 

[Euge]

Equate the limit

$$\lim_{n \to \infty} \frac1{n} \sum_{i = 1}^n \sum_{j = 1}^n \frac1{i + j}$$

Spoiler

We have

$\displaystyle \lim_{n\to \infty} \frac{1}{n}\sum_{i = 1}^n \sum_{j = 1}^n \frac{1}{i + j}$

$\displaystyle = \lim_{n \to \infty} \frac{1}{n^2} \sum_{i = 1}^n \sum_{j = 1}^n \dfrac{1}{\frac{i}{n} + \frac{j}{n}}$

$\displaystyle = \int_0^1 \int_0^1 \frac{1}{x + y} \, dx\, dy$

$\displaystyle = \int_0^1 (\log(1 + y) - \log(y))\, dy$

$\displaystyle = \int_1^2 \log(y)\, dy - \int_0^1 \log(y)\, dy$

$\displaystyle = (y\log(y) - y)|_{y = 1}^2 - (y\log(y) - y)|_{y = 0}^1$

$\displaystyle = [(2 \log(2) - 2) - (\log(1) - 1)] - [(\log(1) - 1)]$

$\displaystyle = (2\log(2) - 1) + 1$

$\displaystyle = 2\log(2)$.

 

[mathbalarka]

Here's a correction to chisigma's solution.

Spoiler

$$\sum_{i = 1}^n \sum_{j = 1}^n \frac1{i + j} = \sum_{k = 2}^{2n} \frac{c_{k, n}}{k}$$

Where $c_{k, n}$ is the number of partitions of $k$ in two parts, each of size at most $n$. chisigma's flaw in the proof was that he assumed $c_{k, n} = k - 1$, which is true if and only if $k \leq n$. For $k > n$, $c_{k, n} = 2n - k + 1$. Thus,

$$\begin{aligned} \sum_{k = 2}^{2n} \frac{c_{k, n}}{k} = \sum_{k = 2}^{n} \frac{k - 1}{k} + \sum_{k = n + 1}^{2n} \frac{2n - k + 1}{k} \, &= \textcolor{red}{\sum_{k = 2}^n 1} - \textcolor{green}{\sum_{k = 2}^n \frac1{k}} - \textcolor{goldenrod}{\sum_{k = n + 1}^{2n} 1} + \textcolor{blue}{\sum_{k = n+1}^{2n} \frac{2n + 1}{k}} \\ &= \textcolor{red}{(n - 1)} \, - \, \textcolor{green}{\left ( H_n - 1 \right )} \, - \, \textcolor{goldenrod}{n} \, + \, \textcolor{blue}{(2n + 1) \left ( H_{2n} - H_n\right )} \\ &= -H_n + (2n + 1)\left ( H_{2n} - H_n \right ) \end{aligned}$$

Using $H_n \sim \log(n)$ and that $\log(n) = o(n)$

$$\lim_{n \to \infty} \frac1n \sum_{i = 1}^n \sum_{j = 1}^n \frac1{i + j} = \lim_{n \to \infty} \frac{(2n+1)( H_{2n} - H_n ) - H_n}{n} = \lim_{n \to \infty} \left [ \left ( 2 + \frac1n \right) \log(2) - \frac{\log(n)}{n}\right ] = 2 \log(2)$$

What could possibly be a better way to puzzle an analyst than solving this problem number theoretically? :D