Approximate summation of the given equation

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

-

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

-
How can we assume that "n" tends to infinity? I mean what if I know that n is some value less than the largest number that be expressed by 32 bits? – user1465557 Aug 21 '14 at 11:47
@user1465557: By letting $n \to \infty$, we see that the factor of $n^3$ converges, so in particular it will stay bounded. In fact it is not hard to see that it will converge monotonously down to the integral. When $n=1$ the constant is the same as yours: $\sqrt{2}$, but when $n=10$, it is approximately $0.82998\dots$, which is not too far from the integral $0.765196\dots$ (calculated by WolframAlpha). – J. J. Aug 21 '14 at 11:53

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

-

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$

-