# upper bound for a sum of inverse index-distances

Consider the following sum:

$$\sum_{i=1}^{n} \sum_{\substack{j=1\\ j\neq i}}^{n} \frac{1}{\vert i-j \vert ^{1/2}} \leq const \; n^\alpha$$

What is a good (i.e. also easy to achieve) and the best possible estimate (i.e. $\alpha$ being as small as possible) for this sum?

-
Do you want to include a multiplicative constant on the right? Also, Hilbert's inequality might be relevant: en.wikipedia.org/wiki/Hilbert's_inequality – user31373 Jul 15 '12 at 13:44

Compare sums to integrals. As mentioned by @Davide Giraudo, the sum to estimate is $2S_n$ with $$S_n=n\sum\limits_{k=1}^n\frac1{\sqrt{k}}-\sum\limits_{k=1}^n\sqrt{k}.$$ For every $k\geqslant1$, $$\frac1{\sqrt{k}}\leqslant\int_{k-1}^k\frac{\mathrm dx}{\sqrt{x}},\qquad\sqrt{k}\geqslant\int_{k-1}^k\sqrt{x}\mathrm dx,$$ hence, summing these, $$S_n\leqslant \int_{0}^n\left(\frac{n}{\sqrt{x}}-\sqrt{x}\right)\mathrm dx=\left[2n\sqrt{x}-\frac23x\sqrt{x}\right]_{x=0}^{x=n}=\frac43n\sqrt{n}.$$ Likewise, for every $k\geqslant1$, $$\frac1{\sqrt{k}}\geqslant\int_{k}^{k+1}\frac{\mathrm dx}{\sqrt{x}},\qquad\sqrt{k}\leqslant\int_{k}^{k+1}\sqrt{x}\mathrm dx,$$ hence, summing these, $$S_n\geqslant \int_{1}^{n+1}\left(\frac{n}{\sqrt{x}}-\sqrt{x}\right)\mathrm dx=\left[2n\sqrt{x}-\frac23x\sqrt{x}\right]_{x=1}^{x=n+1}=\frac43n\sqrt{n}-R_n,$$ with $R_n\geqslant0$ and $R_n\ll n\sqrt{n}$.

This proves the optimal upper bound $Cn^\alpha$ of $2S_n$ is reached for $C=\frac83$ and $\alpha=\frac32$.

-