How find this sum $I_n=\sum_{k=0}^{n}\frac{H_{k+1}H_{n-k+1}}{k+2}$

Solution 1:

There are many nice identities playing here: $$\sum_{j+k=u}\frac{1}{jk}=\frac{2H_{u-1}}{u}\tag{1},$$ $$\sum_{h=1}^{n}\frac{H_h}{h}=\frac{1}{2}\left(H_n^2+H_n^{(2)}\right)\tag{2},$$ $$\sum_{h=1}^{n}\frac{H_{h-1}}{h}=\frac{1}{2}\left(H_n^2-H_n^{(2)}\right)\tag{3},$$ $$\sum_{j=1}^{n}\frac{H_j}{n+1-j}=H_{n+1}^2-H_{n+1}^{(2)}\tag{4}.$$ Proofs: $$(1)\quad \sum_{j+k=u}\frac{1}{jk}=\sum_{j=1}^{u-1}\frac{1}{j(u-j)}=\frac{1}{u}\sum_{j=1}^{u-1}\left(\frac{1}{j}+\frac{1}{u-j}\right)=\frac{2H_{u-1}}{u}.$$ $$(2,3)\quad H_n^2=H_n^{(2)}+2\sum_{j=1}^{n}\frac{1}{j}\sum_{k<j}\frac{1}{k}=H_n^{(2)}+2\sum_{j=1}^{n}\frac{H_{j-1}}{j}=-H_n^{(2)}+2\sum_{j=1}^{n}\frac{H_{j}}{j}.$$ By defining $H_0=0$, we have: $$(4)\quad\sum_{j=1}^{n}\frac{H_j}{n+1-j}=[x^{n+1}]\frac{\log^2(1-x)}{1-x},$$ but we know the series coefficients of $\log^2(1-x)$, so: $$(4)\quad\sum_{j=1}^{n}\frac{H_j}{n+1-j}=\sum_{k=1}^{n+1}\frac{2H_{k-1}}{k}$$ and $(4)$ follows from $(3)$. Now we play a bit with the last identity that Greg Martin proved: $$I_n = \frac{1}{2}\sum_{i+j+k\leq n+3}\frac{1}{ijk}=\frac{1}{2}\sum_{t=3}^{n+3}\sum_{i+j+k=t}\frac{1}{ijk}=\frac{1}{2}\sum_{h=3}^{n+3}\sum_{i=1}^{t-2}\frac{1}{i}\sum_{j+k=t-i}\frac{1}{jk};$$ using $(1)$ we have: $$I_n=\sum_{t=3}^{n+3}\sum_{i=1}^{t-2}\frac{H_{t-i-1}}{i(t-i)}=\sum_{t=3}^{n+3}\frac{1}{t}\sum_{i=1}^{t-2}H_{t-i-1}\left(\frac{1}{i}+\frac{1}{t-i}\right),$$ then re-indexing the inner sum: $$I_n=\sum_{t=3}^{n+3}\frac{1}{t}\sum_{i=1}^{t-2}H_{i}\left(\frac{1}{t-i-1}+\frac{1}{i+1}\right),$$ where: $$\sum_{i=1}^{t-2}\frac{H_i}{i+1}=\sum_{i=1}^{t-1}\frac{H_{i-1}}{i}=\frac{1}{2}\left(H_{t-1}^2-H_{t-1}^{(2)}\right)$$ by $(3)$ and $$\sum_{i=1}^{t-2}\frac{H_i}{t-1-i}=H_{t-1}^2-H_{t-1}^{(2)}$$ by $(4)$. By putting all together we get: $$I_n=\frac{3}{2}\sum_{t=3}^{n+3}\frac{H_{t-1}^2-H_{t-1}^{(2)}}{t}.\tag{5}$$ This gives that $I_n$ behaves like $\frac{1}{2}\log^3 n$.

The part below this line is outperformed by my next answer.

Moreover, summation by parts gives: $$\sum_{k=1}^{m+1}\frac{H_{k-1}^{(2)}}{k}=H_{m}^{(2)}H_{m+1}-\sum_{j=1}^m \frac{H_j}{j^2},$$ $$\sum_{k=1}^{m+1}\frac{H_{k-1}^{2}}{k}=H_{m}^{2}H_{m+1}-\sum_{j=1}^m \frac{(H_j+H_{j-1})H_j}{j}=H_{m}^{2}H_{m+1}-\sum_{j=1}^m \frac{(2H_{j-1}+1/j)(H_{j-1}+1/j)}{j},$$ so: $$\sum_{k=1}^{m+1}\frac{H_{k-1}^{2}}{k}=H_{m}^{2}H_{m+1}-2\sum_{j=1}^{m}\frac{H_{j-1}^2}{j}-3\sum_{j=1}^m\frac{H_{j-1}}{j^2}-H_{m}^{(3)},$$ and rearranging we get: $$\sum_{k=1}^{m+1}\frac{H_{k-1}^{2}}{k}=\frac{1}{3}H_{m}^{2}H_{m+1}+\frac{2H_m^2}{3(m+1)}-\sum_{j=1}^m\frac{H_{j-1}}{j^2}-\frac{1}{3}H_m^{(3)}.$$ By summing everything, we have that $(5)$ can be written in the following form: $$I_{n}=\frac{1}{2}H_{n+2}^2 H_{n+3}+\frac{H_{n+2}^2}{n+3}-\frac{3}{2}H_{n+2}^{(2)}H_{n+3}+H_{n+2}^{(3)}+\frac{3}{2}\sum_{j=1}^{n+2}\frac{H_j}{j^2}.\tag{6}$$ The last sum is now clearly bounded by an absolute constant ($\zeta(3)$, for istance), and I strongly believe that it does not simplify further (I was wrong).

Solution 2:

Not a full answer, but hopefully helpful progress: rewriting $$I_n=\sum_{k=1}^{n+1}\frac{H_{k}H_{n+2-k}}{k+1},$$ we recognize that $$ \sum_{n=0}^\infty I_n x^{n+2} = \bigg( \sum_{k=1}^\infty \frac{H_k}{k+1} x^k \bigg) \bigg( \sum_{k=1}^\infty H_k x^k \bigg). $$ Since $\sum_{j=1}^\infty \frac1j x^j = -\log(1-x)$ and $H_k = \sum_{j=1}^k \frac1j$, we see that $$ \sum_{k=1}^\infty H_k x^k = \frac{-\log(1-x)}{1-x}. $$ Integrating (and forcing the constant term to equal $0$) then gives $$ \sum_{k=1}^\infty \frac{H_k}{k+1} x^{k+1} = \frac{\log^2(1-x)}2. $$ Therefore $$ \sum_{n=0}^\infty I_n x^n = \frac1{x^2} \bigg( \frac1x\frac{\log^2(1-x)}2 \bigg) \bigg( \frac{-\log(1-x)}{1-x} \bigg) = \frac{-\log^3(1-x)}{2x^3(1-x)}. $$

We can use this generating function to try to get information about $\{I_n\}$. For example, if we define $\{c_n\}$ by $$ -\log^3(1-x) = \sum_{n=1}^\infty c_n x^n, $$ then we conclude that $$ I_n = \frac12 \sum_{k=1}^{n+3} c_k. $$ Note that $$ c_n = \sum_{i+j+k=n} \frac1{ijk}, $$ so that $$ I_n = \frac12 \sum_{i+j+k\le n+3} \frac1{ijk}. $$

Solution 3:

Maybe I have got the definitive trick. I recall my previous $(5)$: $$I_n=\frac{3}{2}\sum_{t=3}^{n+3}\frac{H_{t-1}^2-H_{t-1}^{(2)}}{t}.\tag{5}$$ Partial summation gives (I set $H_{0}^{(j)}=0$ for consistency): $$\sum_{n=1}^{m}\frac{H_{n-1}^{(2)}}{n}=H_m H_{m-1}^{(2)}-\sum_{n=1}^{m-1}\frac{H_n}{n^2}=H_m H_m^{(2)}-\sum_{n=1}^m\frac{H_n}{n^2}=H_m H_m^{(2)}-H_{m}^{(3)}-\sum_{n=1}^{m}\frac{H_{n-1}}{n^2}.\tag{7}$$ This leads to: $$I_n=\frac{3}{2}\sum_{t=1}^{n+3}\left(\frac{H_{t-1}^2}{t}+\frac{H_{t-1}}{t^2}\right)+\frac{3}{2}H_{n+3}^{(3)}-\frac{3}{2}H_{n+3}H_{n+3}^{(2)}.\tag{8}$$ Now we have (since $a^3-b^3=(a-b)(a^2+ab+b^2)$): $$H_{j+1}^3-H_{j}^3 = \frac{H_{j+1}^2+H_{j+1} H_j +H_{j}^2}{j+1}=3\frac{H_j^2}{j+1}+3\frac{H_j}{(j+1)^2}+\frac{1}{(j+1)^3}.\tag{9}$$ Summing both sides of $(9)$ with $j$ that runs from $0$ to $n+2$ we have: $$H_{n+3}^3-H_{n+3}^{(3)}=3\sum_{t=1}^{n+3}\left(\frac{H_{t-1}^2}{t}+\frac{H_{t-1}}{t^2}\right).\tag{10}$$ (An alternative proof of $(10)$, always based on partial summation, is given below by Matt Groff)

If now we simply plug $(10)$ into $(8)$ we end with: $$I_n = \frac{1}{2}H_{n+3}^3+H_{n+3}^{(3)}-\frac{3}{2}H_{n+3}H_{n+3}^{(2)},\tag{11}$$ that is way nicer than my previous $(6)$ and perfectly answers the question.

It is worth mentioning that, due to Greg Martin proof, this gives a closed expression for the sum $$\sum_{i+j+k\leq n}\frac{1}{ijk}$$ and for the coefficients of the Taylor series of $\log^4(1-x)$ around zero.

Many many thanks to Greg Martin and Matt Groff for this brilliant piece of cooperative mathematics - should we ask to split the bounty in three?

Solution 4:

Continuing using both Greg Martin and Jack D'Aurizio's answers, I start with:

$$ \begin{align} \sum_{k=1}^{m+1}\frac{(H_{k-1})^2}{k} &= (H_m)^2 H_{m+1} - \sum_{k=1}^m{ \frac{(H_k+H_{k-1} )H_k}{k} } \\ &= (H_m)^2 H_{m+1} - \sum_{k=1}^m{ \frac{ \left( (H_{k-1}+\frac{1}{k}) + H_{k-1} \right)(H_{k-1}+\frac{1}{k})}{k} } \\ &= (H_m)^2 H_{m+1} - \sum_{k=1}^m{ \frac{ \left( 2H_{k-1}+\frac{1}{k}\right)(H_{k-1}+\frac{1}{k})}{k} } \\ &= (H_m)^2 H_{m+1} - \sum_{k=1}^m{ \frac{ 2(H_{k-1})^2+\frac{3}{k}H_{k-1}+\frac{1}{k^2}}{k} } \\ 3\sum_{k=1}^{m+1}\frac{(H_{k-1})^2}{k} &= (H_m)^2 H_{m+1} - \sum_{k=1}^m{ \frac{ \frac{3}{k}H_{k-1}+\frac{1}{k^2}}{k} } \\ &= (H_m)^2 H_{m+1} - \sum_{k=1}^m{ \left( \frac{3}{k^2}H_{k-1}+\frac{1}{k^3} \right) } \\ &= (H_m)^2 H_{m+1} - \sum_{k=1}^m{ \left( \frac{3}{k^2}H_{k-1} \right) } + H_m^{(3)} \end{align} $$