2
$\begingroup$

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?

  • 1
    Do you want to include a multiplicative constant on the right? Also, Hilbert's inequality might be relevant: http://en.wikipedia.org/wiki/Hilbert's_inequality2012-07-15

1 Answers 1

2

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