Approximate summation of the given equation

Question

I have been trying from an hour to approximate the value of $M$ in the equation given below.

$$ M = \sum\limits_{i=1}^n\left(\sum\limits_{j=1}^n\left(\sqrt{ i^2 + j^2 }\right)\right) $$

One thing I know is that $M$ will lie between the range given below by considering two cases, i.e, $(i = j = n)$ and $(i = j = 1)$.

$$ n^2\sqrt{2} \leq M \leq n^3\sqrt{2} $$

But I am not satisfied with this answer because it is a broad range.

What I want is to get an approximate value for $M$ which lies somewhere in between of $O(n^2)$ and $O(n^3)$.

Answer 1

Consider the following:

$$M = \sum_{i=1}^n \sum_{j=1}^n \sqrt{i^2 + j^2} = n^3 \sum_{i=1}^n \sum_{j=1}^n \sqrt{\left(\frac{i}{n}\right)^2 + \left(\frac{j}{n}\right)^2} \cdot \frac{1}{n} \cdot \frac{1}{n}.$$

Now as $n \to \infty$ we have $$\sum_{i=1}^n \sum_{j=1}^n \sqrt{\left(\frac{i}{n}\right)^2 + \left(\frac{j}{n}\right)^2} \cdot \frac{1}{n} \cdot \frac{1}{n} \to \int_0^1 \int_0^1 \sqrt{x^2 + y^2} \, dx \, dy \approx 0.765196 \dots$$

So your sum is indeed of order $n^3$, with the constant approaching that integral.

EDIT: We see that the Riemann sum is always an overestimate for the integral since in the $\frac{1}{n} \times \frac{1}{n}$ grid we pick the point in every square where $\sqrt{x^2 + y^2}$ is highest. Therefore we have $$\left(\int_0^1 \int_0^1 \sqrt{x^2 + y^2} \, dx \, dy\right) n^3 \le M \le \sqrt{2} n^3,$$ with $M/n^3$ tending to the integral as $n \to \infty$.

Answer 2

We have $$ \sum_{j=1}^{n}\sqrt{i^2+j^2}\gt\sum_{j=1}^{n}j=\frac{n(n+1)}{2};i=1,2,\ldots,n $$ so $$ \sum\limits_{i=1}^n\sum\limits_{j=1}^n\sqrt{ i^2 + j^2 }\gt n\frac{n(n+1)}{2}=\frac{1}{2}(n^3+n^2) $$

Answer 3

I do not know how much this could help you but $$M_n = \sum\limits_{i=1}^n\sum\limits_{j=1}^n\sqrt{ i^2 + j^2 } \lt \sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)=n^2+n^3$$ So, as J.J. pointed it it out, the $n^3$ contribution seems to be clear.

By the way, the limiting value, as answered by J.J., is $$\frac{1}{3} \left(\sqrt{2}+\sinh ^{-1}(1)\right)\simeq 0.765195716464$$ You can notice that $M_{100}=0.771674 \times 10^6$ and $M_{1000}=0.765844\times 10^9$