Calculating or estimating a sum of pairs of reciprocals with a constant sum

Question

For given $M$, I would like to find $$\sum_{\stackrel{i + j = M}{i < j}} \frac{1}{i}\frac{1}{j}.$$

I'm solving the problem programatically ATM, with a single for loop for any given $M$, and I want to solve it for all $M \in \{ 2, \ldots, N \}$ for large $N$, say $10^6$ or $10^7$. An approximation would be ok, or a dynammic programming solution. However, solving it using two for loops is not an option, even when $N$ is as small as about $10^4$.

I've tried using formal power series, but I'm really weak in this area, so I couldn't derive the sought expression. Is this the way to go?

Answer 1

We have \begin{align*} \sum_{\substack{i +j = M\\ i < j}} \frac 1{ij} &= \sum_{i=1}^{\lfloor(M-1)/2\rfloor} \frac 1{i(M-i)}\\ &= \frac 1M\sum_{i=1}^{\lfloor(M-1)/2\rfloor} \left(\frac 1{i} + \frac{1}{M-i}\right) \end{align*} For odd $M$ this equals $\frac 1M \sum_{i=1}^{M-1} \frac 1i$, for even $M$ $\frac 1M \sum_{i=1}^{M-1} \frac 1i - \frac 2{M^2}$. Perhaps now it helps that $\sum_{i=1}^n \frac 1i \sim \log n$.

Answer 2

$$\sum_{k=1}^{m-1}\frac{1}{k(m-k)}=\sum_{a+b=m}_{(a,b)\in \mathbb{N^2}}\frac{1}{ab}=\sum_{2a=2b=m}\frac{1}{ab}+\sum_{a+b=m}_{a>b}_{(a,b)\in \mathbb{N^2}}\frac{1}{ab}+\sum_{a+b=m}_{a<b}_{(a,b)\in \mathbb{N^2}}\frac{1}{ab}$$

Thus your sum is equal to:

$$\frac{((-1)^{m}-1)}{m^2}+\frac{1}{m}\sum_{k=1}^{m-1}\frac{1}{k}$$

Which gives an asymptotic of: $$\sum_{\stackrel{i + j = M}{i < j}} \frac{1}{i}\frac{1}{j}=\frac{\ln(m)+\gamma}{m}+\frac{(-1)^{m+1}}{m^2}+O(\frac{1}{m^3})$$

Where $\gamma$ is the Euler–Mascheroni constant $\gamma \approx 0.57721566$

Answer 3

$$\sum_{\stackrel{i+j=M}{i<j}}\frac{1}{i}\frac{1}{j}=\sum_{j=\lfloor M/2\rfloor}^{M-1}\frac{1}{(M-j)j}$$ 1. If $M=2n$ then $$\sum_{\stackrel{i+j=2n}{i<j}}\frac{1}{i}\frac{1}{j}=\sum_{j=n}^{2n-1}\frac{1}{(2n-j)j}$$ 2. If $M=2n+1$ $$\sum_{\stackrel{i+j=2n+1}{i<j}}\frac{1}{i}\frac{1}{j}=\sum_{j=n}^{2n}\frac{1}{(2n+1-j)j}$$