Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

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

share|improve this answer
    
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 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 at 11:53

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$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.