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

$$I_n=\sum_{k=0}^{n}\dfrac{H_{k+1}H_{n-k+1}}{k+2}$$

where $$H_{n}=1+\dfrac{1}{2}+\cdots+\dfrac{1}{n}$$

my try:since $$I_n=\dfrac{1+\dfrac{1}{2}+\cdots+\dfrac{1}{n+1}}{2}+\dfrac{\left(1+\dfrac{1}{2}\right)\left(1+\dfrac{1}{2}+\cdots+\dfrac{1}{n}\right)}{3}+\cdots+\dfrac{1+\dfrac{1}{2}+\cdots+\dfrac{1}{n+1}}{n+2}$$ $$I_n=\dfrac{1+\dfrac{1}{2}+\cdots+\dfrac{1}{n+1}}{n+2}+\dfrac{\left(1+\dfrac{1}{2}\right)\left(1+\dfrac{1}{2}+\cdots+\dfrac{1}{n}\right)}{n+1}+\cdots+\dfrac{1+\dfrac{1}{2}+\cdots+\dfrac{1}{n+1}}{2}$$ so $$2I_n=\left(1+\dfrac{1}{2}+\cdots+\dfrac{1}{n+1}\right)\left(\dfrac{1}{2}+\dfrac{1}{n+2}\right)+\left(1+\dfrac{1}{2}\right)\left(1+\dfrac{1}{2}+\cdots+\dfrac{1}{n}\right)\left(\dfrac{1}{3}+\dfrac{1}{n+1}\right)+\cdots+\left(1+\dfrac{1}{2}+\cdots+\dfrac{1}{n+1}\right)\left(\dfrac{1}{2}+\dfrac{1}{n+2}\right)$$ Maybe this try is not usefull, so I think use other methods to solve it .

Thank you very much!

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

• Sorry for such a simple question, but what is $H_n^{(2)}$? – Matt Groff Jan 10 '14 at 1:25
• $$H_n^{(2)}=\sum_{j=1}^{n}\frac{1}{j^2}.$$ – Jack D'Aurizio Jan 10 '14 at 1:26
• @Jack.D'Aurizio: Your second-to-last equation (before (6) seems to have an error (which gives the last equation an incorrect value, too), according to Mathematica 9.0. I'm trying to figure out what the error is. – Matt Groff Jan 10 '14 at 2:03
• Glad to help - awesome answer! I'm still wondering if we can go simpler/better... – Matt Groff Jan 10 '14 at 2:29
• I looked into summation-by-parts, then tried expanding the r.h.s. sum in your comment into a function of $H_{k-1}$. It seems this may work... I'm posting a partial answer to show what I've done so far. – Matt Groff Jan 10 '14 at 3:49

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

• very helpful, indeed. The last identity is wonderful! – Jack D'Aurizio Jan 10 '14 at 1:46

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?

• I don't feel that I contributed significantly enough to receive part of the bounty. Besides, working together with you was a far better reward! – Matt Groff Jan 10 '14 at 16:54
• It's enough just to see my name a couple of times :) I'm happy not receiving any of the bounty. By the way, did you numerically check the final formula against the original problem, just to verify that there wasn't a typo anywhere along the way? – Greg Martin Jan 10 '14 at 21:11
• (I think it'd be interesting to see if redoing the entire proof in the language of generating functions made it noticeably more compact.) – Greg Martin Jan 10 '14 at 21:16
• @Greg Martin: yes, I numerically checked my formula and it looks fine. It would be interesting to reformulate the solution in terms of generating functions only, but I believe some points are easier to grasp in a purely combinatorial fashion, like $\sum_{j=1}^n\frac{H_j^{(k)}}{j^k}=\frac{1}{2}\left(H_n^{2k}+H_n^{(2k)}\right).$ Maybe the shortest proof is a tricky combination of the two approaches (I also used the generating functions method to prove my $(4)$, for instance). – Jack D'Aurizio Jan 11 '14 at 14:20
• @Matt Groff: many thanks for the additional bounty! – Jack D'Aurizio Feb 10 '14 at 14:14

\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}