Compute $\lim \limits_{n\to \infty} \frac{1}{n}\sum_{i,j=1}^n\frac{1}{\sqrt{i^2+j^2}}$.
I am not looking for a solution using double integrals. I tried to turn this into a Riemann sum, but I couldn't make any progress.
I thought about using the squeeze theorem, but I can't find any useful inequalities, I just tried to use AM-GM on the denominator, but it didn't help.
Edit: This is definitely solveable without double integrals, it comes from a high school book and here multivariate calculus isn't covered.
Compute $\lim \limits_{n\to \infty} \frac{1}{n}\sum_{i,j=1}^n\frac{1}{\sqrt{i^2+j^2}}$
integrationlimits
Related Solutions
Table of Content.
- Heuristic argument
- Elementary proof, version 1.
- Elementary proof, version 2. (NEW!)
1. Heuristic argument.
Although far from being rigorous, one can provide a heuristic computation which explains why we expect the answer to be $\frac{1}{2}$. Notice that
$$ \frac{n^{n+j}/(n+j)!}{n^n / n!} = \begin{cases} \prod_{k=1}^{j} \frac{n}{n+k}, & j \geq 1 \\ 1, & j = 0, -1 \\ \prod_{k=1}^{-j-1} \frac{n-k}{n}, & j \leq -2 \end{cases} $$
In any of cases, taking logarithm and applying the approximation $\log(1+x) \approx x$ shows that the above quantity is approximately $e^{-j^2/2n}$. So
$$ e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!} = \frac{\sum_{j=-n}^{0} \frac{n!}{n^n \sqrt{n}} \frac{n^{n+j}}{(n+j)!} }{\sum_{j=-n}^{\infty} \frac{n!}{n^n \sqrt{n}}\frac{n^{n+j}}{(n+j)!} } \approx \frac{\sum_{j=-n}^{0} e^{-(j/\sqrt{n})^2/2} \frac{1}{\sqrt{n}} }{\sum_{j=-n}^{\infty} e^{-(j/\sqrt{n})^2/2} \frac{1}{\sqrt{n}} } \approx \frac{\int_{-\infty}^{0} e^{-x^2/2} \, dx}{\int_{-\infty}^{\infty} e^{-x^2/2} \, dx} = \frac{1}{2}. $$
Most of the solutions that I know is more or less a rigorous realization of this kind of observation, and so, it is either involved or requiring extra knowledge.
2. Elementary proof, version 1.
Define $A_n$, $B_n$ and $C_n$ by
$$ A_n := e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}, \qquad B_n := e^{-n} \sum_{k=n+1}^{\infty} \frac{n^k}{k!}, \qquad C_n = \frac{n^{n} e^{-n}}{n!}. $$
From the Taylor expansion of the exponential function, we know that $A_n + B_n = 1$. In order to show the desired convergence, it suffices to show that the following claim holds.
Claim. $A_n/B_n \to 1$ as $n\to\infty$.
Indeed, once this is proved, then both $A_n$ and $B_n$ converge to $\frac{1}{2}$ as $n\to\infty$.
Proof of Claim. Using the substitution $k = n-j$ followed by $p = j-1$, one may write
\begin{align*} \frac{A_n}{C_n} &= \sum_{j=0}^{n} \frac{n!}{(n-j)!n^j} = 2 + \sum_{p=1}^{n-1} \prod_{l=1}^{p} \left( 1 - \frac{l}{n} \right). \end{align*}
Similarly, applying the substitution $k = n+p$, one may write
\begin{align*} \frac{B_n}{C_n} &= \sum_{p=1}^{\infty} \frac{n!n^p}{(n+p)!} = \sum_{p=1}^{\infty} \prod_{l=1}^{p} \left( \frac{1}{1 + \frac{l}{n}} \right). \end{align*}
1. Estimation of leading sums. Fix $\alpha \in \left( 0, \frac{1}{3} \right)$ and set $N = N(\alpha) = \left\lceil n^{(1+\alpha)/2} \right\rceil$. Then using the asymptotic formula $1+x = e^{x+\mathcal{O}(x^2)}$ as $x \to 0$, for $1 \leq p \leq N$ we have
$$ \prod_{l=1}^{p} \left( 1 - \frac{l}{n} \right) = \exp\left\{ -\frac{p^2}{2n} + \mathcal{O}\left( n^{-(1-3\alpha)/2} \right) \right\} = \prod_{l=1}^{p} \left( \frac{1}{1 + \frac{l}{n}} \right). $$
In particular, there exists a constant $C > 0$, depending only on $\alpha$, such that
$$ \max\Bigg\{ \prod_{l=1}^{N} \left( 1 - \frac{l}{n} \right), \prod_{l=1}^{N} \left( \frac{1}{1 + \frac{l}{n}} \right) \Bigg\} \leq C e^{-\frac{1}{2}n^{\alpha}}. $$
2. Estimation of tail sums. In this time, consider $p > N$. Then we have
$$ \prod_{l=1}^{p} \left( 1 - \frac{l}{n} \right) \leq C e^{-\frac{1}{2}n^{\alpha}} \left( 1 - \frac{N}{n} \right)^{p-N} \quad \text{and} \quad \prod_{l=1}^{p} \left( \frac{1}{1 + \frac{l}{n}} \right) \leq C e^{-\frac{1}{2}n^{\alpha}} \left( \frac{1}{1 + \frac{N}{n}} \right)^{p-N}. $$
So the tail sum for $A_n/C_n$ can be bounded from above by
$$ \sum_{p=N+1}^{n-1} \prod_{l=1}^{p} \left( 1 - \frac{l}{n} \right) \leq Ce^{-\frac{1}{2}n^{\alpha}} \sum_{k = 0}^{\infty} \left( 1 - \frac{N}{n} \right)^k \leq \frac{Cn}{N} e^{-\frac{1}{2}n^{\alpha}} \leq Cn^{(1-\alpha)/2} e^{-\frac{1}{2}n^{\alpha}}, $$
and likewise,
$$ \sum_{p=N+1}^{\infty} \prod_{l=1}^{p} \left( \frac{1}{1 + \frac{l}{n}} \right) \leq Ce^{-\frac{1}{2}n^{\alpha}} \sum_{k = 0}^{\infty} \left( 1 - \frac{N}{N+n} \right)^k \leq \frac{2Cn}{N} e^{-\frac{1}{2}n^{\alpha}} \leq 2Cn^{(1-\alpha)/2} e^{-\frac{1}{2}n^{\alpha}}. $$
3. Conclusion. Combining altogether,
$$ \frac{A_n}{B_n} = \frac{\left( 1 + o(1) \right) \sum_{p=1}^{N} e^{-\frac{p^2}{2n}} + \mathcal{O}(1)}{\left( 1 + o(1) \right) \sum_{p=1}^{N} e^{-\frac{p^2}{2n}} + o(1)}, $$
which can be easily shown to converge to $1$ as $n\to\infty$, since $\sum_{p=1}^{N} e^{-\frac{p^2}{2n}} \geq \sqrt{n} \, e^{-1/2} \to \infty$ as $n\to\infty$. (In fact, this sum is $(1+o(1))\sqrt{\pi n/2}$ as $n\to\infty$.)
3. Elementary proof, version 2.
In this answer, we do appeal to the concentration behavior of the sum, but rather utilize a mysterious identity from combinatorics.
Write $A_n = e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}$ for the sequence of our interest. We also introduce the following auxiliary sequences:
$$ a_n = \frac{n^n}{n!e^n}, \qquad b_n = (-1)^n \binom{-1/2}{n} = \frac{1}{4^n} \binom{2n}{n}, $$
Before proceeding, we make some observations. The key ingredients are the following identities
$$ A_n = \sum_{k=0}^{n} a_k a_{n-k}, \qquad 1 = \sum_{k=0}^{n} b_k b_{n-k}. $$
The former one is quite non-trivial, and a proof can be found here. On the other hand, the latter one is easily proved by comparing both sides of $ \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} = \left( \frac{1}{\sqrt{1-x}} \right)^2 = \left( \sum_{n=0}^{\infty} b_n x^n \right)^2$. Next, we have the following observation.
Lemma. $ \frac{a_n}{b_n} \to \frac{1}{\sqrt{2}} $ as $n\to\infty$.
This lemma tells that, roughly $a_{k}a_{n-k} \approx \frac{1}{2} b_k b_{n-k}$ and hence $ A_n \approx \frac{1}{2} \sum_{k=0}^{n} b_k b_{n-k} = \frac{1}{2}$. Indeed, this is an instance of the philosophy that `limit should be preserved under averaging', and so, it can be proved by a standard machinery. We separate the rigorous claim into a standalone result:
Proposition. Let $(a_n), (b_n)$ be sequences in $(0, \infty)$ such that
- $a_n/b_n \to \ell \in (0, \infty)$;
- $b_n \to 0$ as $n\to\infty$;
- $\sum_{k=0}^{n} b_k b_{n-k} = 1$ for all $n$.
Then $\sum_{k=0}^{n} a_k a_{n-k} \to \ell^2$ as $n\to\infty$.
Therefore, $A_n \to \frac{1}{2}$ is a direct consequence of this proposition together with the well-known fact that $b_n \to 0$. Indeed, this can be proved as follows:
$$ b_n^2 = \left( \frac{1 \cdot 3 \cdots (2n-1)}{2 \cdot 4 \cdots (2n)} \right)^2 = \left( \frac{1 \cdot 3}{2 \cdot 2} \right) \left( \frac{3 \cdot 5}{4 \cdot 4} \right) \cdots \left( \frac{(2n-3)(2n-1)}{(2n-2)(2n-2)} \right) \frac{2n-1}{4n^2} \leq \frac{1}{2n}. $$
Finally, we prove the claims above.
Proof of Lemma. Using the identity $-\int_{0}^{1} \frac{u}{a+u} \, du = a \log (a+1) - a \log a - 1$ for $a > 0$, we notice that
\begin{align*} &- \sum_{k=1}^{n} \int_{0}^{1} \frac{u}{n+k-1+u} \, du \\ &= \sum_{k=1}^{n} \left[ (n+k-1)\log (n+k) - (n+k-1)\log(n+k-1) - 1 \right] \\ &= (2n)\log(2n) - n \log n - n - \sum_{k=1}^{n} \log(n+k) \\ &= \log \left[ \left( \frac{4n}{e} \right)^n \frac{n!}{(2n)!} \right] = \log \left( \frac{a_n}{b_n} \right). \end{align*}
Then, using $ \frac{1}{2(n+k)} \leq \int_{0}^{1} \frac{u}{n+k-1+u} \, du \leq \frac{1}{2(n+k-1)} $, we obtain
$$ -\frac{1}{2}\sum_{k=1}^{n} \frac{1}{n+k-1} \leq \log \left( \frac{a_n}{b_n} \right) \leq -\frac{1}{2}\sum_{k=1}^{n} \frac{1}{n+k}. $$
Therefore the conclusion follows from the well-known limit $ \sum_{k=1}^{n} \frac{1}{1+\frac{k}{n}} \frac{1}{n} \to \int_{0}^{1} \frac{dx}{1+x} = \log 2$.
Proof of Proposition. Let $\alpha, \beta $ satisfy $0 < \alpha < \ell < \beta$. Then there exists $N$ such that $\alpha \leq \frac{a_n}{b_n} \leq \beta$ for all $n \geq N$. So, if $n \geq 2N$, then
$$ \alpha^2 \sum_{k=N}^{n-N} b_k b_{n-k} \leq \sum_{k=N}^{n-N} a_k a_{n-k} \leq \beta^2 \sum_{k=N}^{n-N} b_k b_{n-k}. $$
Now let $M > 0$ be a bound of $a_n/b_n$. Since $b_n \to 0$ as $n\to\infty$, we have
$$ \sum_{k=0}^{N-1} a_k a_{n-k} + \sum_{k=n-N+1}^{n} a_k a_{n-k} = 2\sum_{k=0}^{N-1} a_k a_{n-k} \leq 2M^2 \sum_{k=0}^{N-1} b_k b_{n-k} \xrightarrow[n\to\infty]{} 0 $$
Combining altogether and using $1 = \sum_{k=0}^{n} b_k b_{n-k}$,
$$ \alpha^2 \leq \liminf_{n\to\infty} \sum_{k=0}^{n} a_k a_{n-k} \leq \limsup_{n\to\infty} \sum_{k=0}^{n} a_k a_{n-k} \leq \beta^2. $$
Letting $\alpha \uparrow \ell$ and $\beta \downarrow \ell$ proves the desired identity.
We conclude with some remarks.
Remark. If we do not care about elementary solution, this approach can be simplified by showing that
- $A_n$ is bounded and decreasing, hence converges.
By the identity $A_n = \sum_{k=0}^{n} a_k a_{n-k}$, we have
$$ (1-x) \sum_{n=0}^{\infty} A_n x^n = \left( \frac{\sum_{n=0}^{\infty} a_n x^n}{\sum_{n=0}^{\infty} b_n x^n} \right)^2, $$
hence by a version of abelian theorem, we obtain
$$ \lim_{n\to\infty} A_n = \lim_{n\to\infty} \left( \frac{a_n}{b_n} \right)^2 = \frac{1}{2}. $$
There is another elementary way to get going. First, notice that: $$\cos x - \sin x = \sqrt{2}\sin(\pi/4 - x).$$ Therefore, your integral, which we denote by $I_n$ is equal to: $$I_n = n2^{\frac n2}\int_0^1\sin^n(\pi/4 - x)dx.$$ On the other hand, you can use integration by parts twice to show that:
$$\int\sin^nxdx = \frac{-\cos x \hspace{3pt} \sin^{n-1}x}{n} + \frac{(n-1)}{n} \int \sin^{n-2} x dx.$$
You can combine these two to obtain an explicit formula for $I_n.$
Update: This turned out to be interesting if we restrict ourselves to only elementary calculus. First, write: $$I_n = n2^{n/2}\int_0^{\tfrac{\pi}{4}}\sin^n\left(\frac{\pi}{4}-x\right)dx+n2^{n/2}\int_{\tfrac{\pi}{4}}^1\sin^n\left(\frac{\pi}{4}-x\right)dx = $$ $$ = n2^{n/2}\int_0^{\tfrac{\pi}{4}}\sin^n\left(x\right)dx+n2^{n/2}\int_{\tfrac{\pi}{4}-1}^0\sin^n\left(x\right)dx = A_n+B_n.$$ Now, using $\sin x\leq x:$ $$|B_n|\leq n2^{n/2}\int_{\tfrac{\pi}{4}-1}^0|\sin^n\left(x\right)|dx=n2^{n/2}\int^{1-\tfrac{\pi}{4}}_0\sin^n\left(x\right)dx\leq$$ $$\dfrac{n}{n+1}\left(1-\dfrac{\pi}{4}\right)\left(\sqrt{2} - \dfrac{\pi}{2\sqrt{2}}\right)^n\to 0.$$ Therefore, we simply need to study $A_n,$ which satisfies a rather simple recurrence relation (from integration by parts): $$A_n = \dfrac{2n-2}{n-2}A_{n-2} - 1,\,\, A_1 = \sqrt{2}-1,\,\, A_2 = \dfrac{\pi}{2}-1.$$
Numerical evidence suggests that $A_n$ is positive, increasing and converging to $1$ as desired. Moreover, odd indices are of the form $\sqrt{2}a_n-b_n$ and the even indices are of the form $\pi c_n -d_n,$ where $a_n,b_n,c_n,d_n$ are all positive integers. In fact, one can easily find a closed form for $a_n:$ $$a_n = \dfrac{2^{3n}(n!)^2}{(2n)!},$$ while the closed form for $b_n$ seems to be very difficult, if possible at all.
However, based on what I have tried, finishing using only elementary approach from here seems rather difficult. A naive method is to use induction to prove the monotonicity. But that amounts to showing the following estimate: $$A_n>\dfrac{n}{n+2}$$ or equivalently: $$\int^{\tfrac{\pi}{4}}_0\sin^n\left(x\right)dx>\dfrac{1}{2^{n/2}(n+2)} (\dagger)$$ But above seems tricky as using the naive inequality $\sin(x)\geq\dfrac{2\sqrt{2}}{\pi}x$ on $[0,\pi/4]$ proves to be a too crude. I tried strenghtening it further by using: $$\sin(x)\geq \dfrac{3}{\pi}x\cdot 1_{[0,\pi/6]}+\left(\dfrac{6(\sqrt{2}-1)}{\pi}x+\dfrac{3-2\sqrt{2}}{2}\right)\cdot 1_{[\pi/6, \pi/4]}$$ which was again too strong.
Lastly, one can technically find a explicit formula by doing the following: $$\dfrac{A_{2n+1}}{(2n+1)2^n\sqrt{2}} = -\int_0^{\tfrac{\pi}{4}}(\sin^2(x))^nd(\cos x) = \int_{\tfrac{1}{\sqrt{2}}}^1(1-t^2)^ndt = $$ $$\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}\cdot\dfrac{1-2^{-k-\frac 12}}{2k+1}.$$ But again, this is not the nicest looking sum to manipulate.
Update: An elementary proof was found in this question and it was just a repeated application of integration by parts. Namely, \begin{align}\int_0^{1/\sqrt{2}}\frac{t^n\,dt}{(1-t^2)^{1/2}}&=\frac{1}{n+1}\left(\left.\frac{t^{n+1}}{(1-t^2)^{1/2}}\right|_0^{1/\sqrt{2}}-\int_0^{1/\sqrt{2}}\frac{t^{n+2}\,dt}{(1-t^2)^{3/2}}\right)\\&=\frac{1}{n+1}\left(2^{-n/2}-\frac{1}{n+3}\left.\frac{t^{n+3}}{(1-t^2)^{3/2}}\right|_0^{1/\sqrt{2}}+\ldots\right)\\&>\frac{2^{-n/2}}{n+1}\left(1-\frac{1}{n+3}\right)=2^{-n/2}\frac{n+2}{(n+2)^2-1}>\dfrac{2^{n/2}}{n+2}.\end{align} Thus, the proof is complete and should completely fall in the elementary calculus scope.
Best Answer
Denote the limit you have to compute by $L$.
We may apply the Stolz-Cesaro theorem to get that $L=\lim\limits_{n\to \infty}\left(2\sum_{i=1}^{n-1}\frac{1}{\sqrt{n^2+i^2}}+\frac{1}{\sqrt{2n^2}}\right)$.
Since $\lim\limits_{n\to \infty}\frac{1}{\sqrt{2n^2}}=0$ and $\lim\limits_{n\to \infty}\sum_{i=1}^{n-1}\frac{1}{\sqrt{n^2+i^2}}=\int\limits_0^1\frac{dx}{\sqrt{x^2+1}}=\ln(1+\sqrt 2)$, we get that $L=2\ln(1+\sqrt 2)$.