This is a natural extension of the question Sum of Squares of Harmonic Numbers. I became interested in this question while studying the problem A closed form of $\sum_{n=1}^\infty\left[ H_n^2-\left(\ln n+\gamma+\frac1{2n} \right)^2\right]$, especially the variation with a general integer power $q$, of which the present question is a part.
Let the sum in question be
$$s(q,n) = \sum _{k=1}^n H_k^{q} \tag{1}$$
where $q = 1, 2, 3, …$ and $H_k = 1 + 1/2 + … + 1/k$ is the harmonic number.
Problems
- Derive a recursion relation for $s(q,n)$
- Calculate $s(q,n)$ for $q=1 .. 4$
- Discuss similarities with and possible deviation from the corresponding integrals $i(q,n)=\int_1^n ln(k)^q \, dk$
- Discuss the possible meaning of the term "closed form" in the present context of finite sums.
I have given an answer to 1. and 2. up to q = 4, and 3. correspondingly.
Question 4. is perhaps the most interesting, and I have started to answer it.
Best Answer
The sum for which we wish to find a closed expression is
$$s(q,n) = \sum _{k=1}^n H_k^{q} \tag{1}$$
where $q = 1, 2, 3, ...$ and $H_k = 1 + 1/2 + ... + 1/k$ is the harmonic number.
1. Recursion relation
$s(q,n)$ satisfies this recursion relation
$$s(q,n) = H_n s(q-1,n) - \sum _{m=1}^n \frac{1}{m} s(q-1,m-1) \tag{2}$$
with the boundary conditions
$$s(0,n)=n, s(q,0)=0 \tag{2a}$$
Derivation
Splitting one factor $H_k$ off from the power we can write
$$s(q,n) = \sum _{k=1}^n H_k^{q} = \sum _{k=1}^n H_k^{q-1}\;H_k$$
Inserting $H_k = \sum _{m=1}^k \frac{1}{m}$ this becomes
$$s(q,n) = \sum _{k=1}^n H_k^{q-1}\sum _{m=1}^k \frac{1}{m}$$
Exchanging the order of summation gives
$$s(q,n) =\sum _{m=1}^n \frac{1}{m} \sum _{k=m}^n H_k^{q-1}$$
This can be written as
$$s(q,n) =\sum _{m=1}^n \frac{1}{m} (\sum _{k=1}^n H_k^{q-1} - \sum _{k=1}^{m-1} H_k^{q-1})$$
which using $(1)$ gives $(2)$.
Notice that this derivation is different from Abelian partial summation.
The boundary conditions follow directly from the definition $(1)$.
2. The sum for particular values of q
We also give the corresponding integral over the power of ln(n) (see 3. below).
From $(2)$ we obtain easily
$$s(1,n)=(n+1) H_n-n \tag{3}$$ $$i(1,n)=n \ln (n) -n +1 \tag{3a}$$ and
$$s(2,n)=(n+1) H_n^{2}-(2 n+1) H_n+2 n \tag{4}$$ $$i(2,n)=n \ln ^2(n)-2 n \ln (n) +2 n-2 \tag{4a}$$
Slightly more effort is required for $q = 3$ which gives
$$s(3,n) = (n+1) H_n^{3}-(3 n+1) H_n^{2}+(6 n+3) H_n-6 n - \frac{1}{2} \left( H_n^{2}-H_n^{(2)} \right)\tag{5}$$ $$i(3,n)=n \ln ^3(n)-3 n \ln ^2(n)+6 n \ln (n) - 6 n+6 \tag{5a}$$
where we encounter the harmonic sum of second order
$$H_n^{(2)} = \sum _{m=1}^n \frac{1}{m^{2}} \tag{5b}$$
and the curious term
$$\sum _{k=1}^n \frac{H_{k-1}}{k}=\frac{1}{2} \left(H_n^2-H_n^{(2)}\right)\tag{5c}$$
which is also the sum of the terms $1/(i\; j)$ above the diagonal, i.e. for $1\le i<j\le n$.
In the case $q=4$ we find (notice that (6) is preliminary, see (6e) below for a more satisfactory result)
$$s(4,n) =(n+1) H_n^4-\left(4 n+\frac{3}{2}\right) H_n^3+(12 n+6) H_n^2-(24 n+12) H_n+24 n+\left(\frac{1}{2}H_n-2\right) H_n^{(2)}-\frac{3}{2}s_{41}(n)-\frac{1}{2}s_{42}(n)\tag{6}$$
$$i(4,n) = n \ln ^4(n)-4 n \ln ^3(n)+12 n \ln ^2(n)-24 n \ln (n) + 24 n-24\tag{6a}$$
We encouter two new sums which we express via some "canonical" forms $h_i$of sums
$$s_{41}(n)=\sum _{m=1}^n \frac{H_{m-1}^2}{m} = h_1(n) - 2 h_2(n) + h_3(n)\tag{6c}$$
$$s_{42}(n)=\sum _{m=1}^n \frac{H_{m-1}^{(2)}}{m} = h_4(n) - h_3(n)\tag{6d}$$
Where
$$h_1(n) = \sum _{k=1}^n \frac{H_k^2}{k}\tag{7a}$$ $$h_2(n) = \sum _{k=1}^n \frac{H_k}{k^2}\tag{7b}$$ $$h_3(n) = \sum _{k=1}^n \frac{1}{k^3}\tag{7c}$$ $$h_4(n)=\sum _{k=1}^n \frac{H_k^{(2)}}{k}\tag{7d}$$
We have
$$h_3(n) = H_n^{(3)}\tag{7e}$$
and it was shown in [1] that
$$h_1(n) - h_2(n) = \frac{1}{3} (H_n^3 - H_n^{(3)})\tag{8a}$$
and
$$h_4(n)=-h_2(n)+H_n H_n^{(2)}+H_n^{(3)}\tag{8b}$$
so that only one of the three sums $h_1$, $h_2$, and $h_4$ is independent.
Selecting $h_2$ as the independent new term we obtain for $s(4,n)$ the simplified expression
$$s(4,n)=(n+1) H_n^4-(4 n+2) H_n^3+(12 n+6) H_n^2-(24 n+12) H_n+24 n\;+(2 h_2(n)-2 H_n^{(2)}-H_n^{(3)})\tag{6e}$$
Notice that the additional term in brackets is bounded for $n\to\infty$.
In fact, it is easy to see (using robjohn's result for $h_2$ in the solution to [1]) that
$$\lim_{n\to \infty } \, (2 h_2(n)-2 H_n^{(2)}-H_n^{(3)})=4 \zeta(3) -2\zeta(2)-\zeta(3) = 3\zeta(3)-2\zeta(2)=0.316303...\tag{6f}$$
Derivation
The derivation of the formulae for the sum of the powers is straightforward using the recursion relation but it is tedious and must be done carefully.
(8a) was derived in [1]
(8b) is easy to prove by induction. The derivation, however, is more laborious and will be given here using the method of exchanging the order of summation in the double sum which is obtained after entering the definition of $H_k^{(2)}$
$$ \begin{align} \sum _{k=1}^n \frac{H_k^{(2)}}{k} &=\frac{1}{1} (1)\tag{9a}\\ &+ \frac{1}{2}(1+\frac{1}{2^2})\\ &+ \frac{1}{3}(1+\frac{1}{2^2}+\frac{1}{3^2})\\ &+ ... \\ &+ \frac{1}{n}(1+\frac{1}{2^2}+\frac{1}{3^2}+ ...+\frac{1}{n^2} )\\ &=\frac{1}{1^2} H_n +\frac{1}{2^2}(H_n-H_1)+\frac{1}{3^2}(H_n-H_2)+ ... +\frac{1}{n^2}(H_n-H_{n-1}) \tag{9b}\\ &=\sum _{k=1}^{n} \frac{1}{k^2}(H_n-H_{k-1})\\ &=H_n^{(2)}H_n - \sum _{k=1}^n \frac{1}{k^2} (H_k-\frac{1}{k})= H_n^{(2)}H_n-h_2(n) + H_n^{(3)}\tag{9c}\\[9pt] \end{align} $$
Explanation:
$\text{(9a)}$: replace $H_k^{(2)}$ by it definition (5b) an write down the sum like in the following lines
$\text{(9b)}$: Exchange the order of summation, i.e. sum vertically, and take care of the triangular shape of the array of summands
$\text{(9c)}$: identify known sums, let $H_{k-1} = H_k -\frac{1}{k}$, expand, and identify knows sums again.
Derivation of $\text{(8b)}$ completed.
3. The integral of powers of $ln(n)$
Jack d'Aurizio observed in [2] that the integrals
$$i(q,n)=\int_1^n ln(k)^q \, dk\tag{10}$$
(for $q = 1$ and $q = 2$) have a close similarity to the corresponding sums.
In fact
$$i(1,n)=n \ln (n) -n +1 \tag{3a}$$ $$i(2,n)=n \ln ^2(n)-2 n \ln (n) +2 n-2 \tag{4a}$$ $$i(3,n)=n \ln ^3(n)-3 n \ln ^2(n)+6 n \ln (n) - 6 n+6 \tag{5a}$$ $$i(4,n) = n \ln ^4(n)-4 n \ln ^3(n)+12 n \ln ^2(n)-24 n \ln (n) + 24 n-24\tag{6a}$$
It is not difficult to see that in general
$$i(k,n)=(-1)^{m+1} m!+\sum _{k=0}^m (-1)^k n \binom{m}{k} \ln^{m-k}(n)\tag{11}$$
It is interesting that already for $q=3$ this similarity is "spoiled" by the term (5c)
For $q=4$ other types of "spoiler" terms appear (see above).
4. The meaning of "closed form"
As we are dealing with finite sums here these could themselves be called closed forms. But, of course we want to have something "shorter" than the original expression.
We can already see some structure in the cases up to the fourth power: guided by the correponding integral we find for $s(q,n)$ a linear combination of all powers of $H_n$ from zero to $q+1$ the coefficients are linear in $n$. Starting from $q=3$, however, "new" types of sums appear: harmonic numbers of higher order and additional "correction" terms (relative to the ln-integral)which are still under study here.
We could tentatively define "closed expression" here as being a "short" linear combination of expressions within a (hopefully) finite class $v$ of sums, we can call basic elements.
Specific question: Is it sufficient to have these two basic elements
$$v = (H_{n}, H_{n}^{(m)})$$
or is, for instance $h_1$ or, equivalently $h_2$ or $h_4$
also a basic element which must be added to $v$?
5. References
$\text[1]$ Is there a closed form for $\sum _{k=1}^n \frac{1}{k}H_{k-1}^2$?
$\text[2]$ A closed form of $\sum_{n=1}^\infty\left[ H_n^2-\left(\ln n+\gamma+\frac1{2n} \right)^2\right]$