Closed form or approximation of $\sum\limits_{i=0}^{n-1}\sum\limits_{j=i + 1}^{n-1} \frac{i + j + 2}{(i + 1)(j+1)} (i + 2x)(j +2x)$

Question

During the solution of my programming problem I ended up with the following double sum:

$$\sum_{i=0}^{n-1}\sum_{j=i + 1}^{n-1} \frac{i + j + 2}{(i + 1)(j+1)}\cdot (i + 2x)(j +2x)$$

where $x$ is some number. Because of the double sum the complexity of the problem will be quadratic (and I have $n$ at the scale of a million), but if I can find a closed form solution, it will reduce dramatically (log or even something close to constant).

After trying to simplify the sum using the fact that $ \frac{i + j + 2}{(i + 1)(j+1)} = \frac{1}{i+1} + \frac{1}{j+1}$ I think that my knowledge is not enough.

Can anyone help me to simplify this problem (or may be find a reasonable approximation)?

Answer 1

$$ \begin{align} &\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}\frac{i+j+2}{(i+1)(j+1)}\cdot(i+2x)(j+2x)\tag{1}\\ &=\sum_{j=0}^{n-1}\sum_{i=j+1}^{n-1}\frac{i+j+2}{(i+1)(j+1)}\cdot(i+2x)(j+2x)\tag{2}\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{i-1}\frac{i+j+2}{(i+1)(j+1)}\cdot(i+2x)(j+2x)\tag{3}\\ &=\small\frac12\left(\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\frac{i+j+2}{(i+1)(j+1)}\cdot(i+2x)(j+2x)-\sum_{i=0}^{n-1}\frac{2i+2}{(i+1)^2}\cdot(i+2x)^2\right)\tag{4}\\ &=\small\frac12\left(\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\left(\frac1{i+1}+\frac1{j+1}\right)(i+2x)(j+2x)-2\sum_{i=0}^{n-1}\frac1{i+1}\cdot(i+2x)^2\right)\tag{5}\\ &=\small\frac12\left(2\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\frac1{i+1}\cdot(i+2x)(j+2x)-2\sum_{i=0}^{n-1}\frac1{i+1}\cdot(i+2x)^2\right)\tag{6}\\ &=\small\sum_{i=0}^{n-1}\frac1{i+1}\cdot(i+2x)\left(\frac{n(n-1)}2+2nx\right)-\sum_{i=0}^{n-1}\frac1{i+1}\cdot(i+2x)^2\tag{7}\\ &=\small\left(\frac{n(n-1)}2+2nx\right)(n+(2x-1)H_n)-\left(\frac{n(n+1)}2+2n(2x-1)+(2x-1)^2H_n\right)\tag{8}\\[6pt] &=\small4(n-1)H_nx^2+\left(2n^2-4n+\left(n^2-3n+4\right)H_n\right)x+\tfrac12\left(n^3-2n^2+3n-\left(n^2-n+2\right)H_n\right)\tag{9} \end{align} $$ Explanation:
$(1)$: original formula
$(2)$: symmetry
$(3)$: change order of summation
$(4)$: average $(1)$ and $(3)$
$(5)$: simplify
$(6)$: symmetry
$(7)$: sum in $j$
$(8)$: write $i+2x=(i+1)+(2x-1)$ and sum in $i$
$(9)$: write as a polynomial in $x$

Answer 2

Using Maple, I get $$ (n+1) H(n) (n+4x-2)(x-1/2) + 2 n (n+2) x + \frac{n^3-3n}{2} $$ where $$H(n) = \sum_{k=1}^n 1/k = \Psi(n+1) + \gamma$$ As $n \to \infty$, $$ H(n) \sim \ln(n) + \gamma + \dfrac{1}{2n} - \dfrac{1}{12n^2} + \dfrac{1}{120 n^4} - \dfrac{1}{252 n^6} + \dfrac{1}{240 n^8} + \ldots $$