3
$\begingroup$

Does the following sum over positive integers have a name/asymptotic closed form?

$$f(n)=\sum_{i,j<n} \left(\frac{1}{i}-\frac{1}{j}\right)^2$$

In particular I'm wondering if it eventually grows linearly or sublinearly

enter image description here

$\endgroup$

3 Answers 3

5
$\begingroup$

$$\sum_{i,j<n}\frac1{i^2}-2\sum_{i<n}\frac1{i}\sum_{j<n}\frac1{j}+\sum_{i,j<n}\frac1{j^2}\approx n\left(\dfrac{\pi^2}3-\psi^{(1)}(n+1)\right)-2(\log n+\gamma)^2.$$

The derivative of the digamma function has an $O(n^{-1})$ behavior.

$\endgroup$
2
$\begingroup$

It's a little easier to discuss the sum if we let $i$ and $j$ go all the way up $n$. We have

$$f(n+1)=\sum_{1\le i,j\le n}\left({1\over i}-{1\over j}\right)^2=2n\sum_{k=1}^n{1\over k}^2-2\left(\sum_{k=1}^n{1\over k} \right)^2=2n\left({\pi^2\over6}-\sum_{k=n+1}^\infty{1\over k^2}\right)-2H_n^2$$

where

$$H_n=\sum_{k=1}^n{1\over k}=\ln n+\gamma+{1\over2n}+O\left(1\over n^2\right)$$

is a familiar estimate for partial sums of the harmonic series and

$$ \begin{align}\sum_{k=n+1}^\infty{1\over k^2} &=\sum_{k=n+1}^\infty{1\over k(k-1)}-\sum_{k=n+1}^\infty{1\over k}\left({1\over k-1}-{1\over k} \right)\\ &=\sum_{k=n+1}^\infty\left({1\over k-1}-{1\over k} \right)-\sum_{k=n+1}^\infty{1\over k^2(k-1)}\\ &={1\over n}-O\left(1\over n^2\right) \end{align}$$

It follows that

$$f(n+1)={\pi^2\over3}n-2-2\left(\ln n+\gamma+{1\over n} \right)^2+O\left(1\over n \right)$$

which might be easiest to think of as

$${\pi^2\over3}n-2(\ln n+\gamma)^2-2+o(1)$$

If you like, since $\ln n =\ln(n-1)+O(1/n)$, this converts to

$$f(n)={\pi^2\over3}n-2(\ln n+\gamma)^2-2-{\pi^2\over3}+o(1)$$

$\endgroup$
1
$\begingroup$

Use $$f(n)=\sum_i\sum_j (A_i-A_j)^2=2n\sum_k A_k^2-2(\sum_k A_k)^2=2n\sum_k \frac{1}{k^2}-2\left(\sum_k\frac{1}{k}\right)^2$$ $$\implies f(n)\sim \frac{n \pi^2}{3}-2(\ln n+\gamma)^2$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .