Harmonic Series

Question

Given a positive integer n, find the closed form of $S(n,m)=\sum_{k=1}^{n} k^mH_{n+k}$ if exists.

Answer

1. Result

$S(n,2)=\sum_{k=1}^{n} k^2H_{n+k}=\frac{n(n+1)(2n+1)}{6}(2H_{2n+1}-H_{n+1})-\frac{10n^3+9n^2+5n}{36}$

$S(n,3)=\sum_{k=1}^{n} k^3H_{n+k}=\frac{n^2(n+1)^2}{4}H_{n+1}+\frac{7n^4+2n^3-7n^2-2n}{48}$

2. Solve $S(n,2)$ and $S(n,3)$

2.1 $S(n,2)=\sum_{k=1}^{n} k^2H_{n+k}$

$$\begin{aligned}S(n,2)&=\sum_{1\leq k\leq n} k^2H_{n+k}\\ &=\sum_{0\leq k< n} (k+1)^2H_{n+k+1}\\ &=\sum_{0}^{n} (x+1)^2H_{n+x+1}\delta x\\ &=[\frac{x(x+1)(2x+1)}{6}H_{n+x+1}]|_{0}^{n}-\sum_{0}^{n}\frac{(x+1)(x+2)(2x+3)}{6}\frac{1}{n+x+2}\delta x\\ &=\frac{n(n+1)(2n+1)}{6}H_{2n+1}-\sum_{0\leq k<n}\frac{(k+1)(k+2)(2k+3)}{6}\frac{1}{n+k+2}\\ &=\frac{n(n+1)(2n+1)}{6}H_{2n+1}-\frac{1}{6}\sum_{0\leq k<n}2k^2-(2n-5)k+2n^2-n+3-\frac{n(n+1)(2n+1)}{n+k+2}\\ &=\frac{n(n+1)(2n+1)}{6}H_{2n+1}\\ &\ \ \ \ \ -\frac{1}{6}\sum_{1\leq k\leq n}2(k-1)^2-(2n-5)(k-1)+2n^2-n+3-\frac{n(n+1)(2n+1)}{n+k+1}\\ &=\frac{n(n+1)(2n+1)}{6}H_{2n+1}-\frac{10n^3+9n^2+5n}{6}+\frac{n(n+1)(2n+1)}{6}\sum_{1\leq k\leq n}\frac{1}{n+k+1}\\ &=\frac{n(n+1)(2n+1)}{6}(H_{2n+1}+\sum_{1\leq k\leq n}\frac{1}{n+k+1})-\frac{10n^3+9n^2+5n}{36}\\ &=\frac{n(n+1)(2n+1)}{6}(2H_{2n+1}-H_{n+1})-\frac{10n^3+9n^2+5n}{36} \end{aligned}$$

2.2 $S(n,3)=\sum_{k=1}^{n} k^3H_{n+k}$

$$\begin{aligned}S(n,3)&=\sum_{1\leq k\leq n} k^3H_{n+k}\\ &=\sum_{0\leq k< n} (k+1)^3H_{n+k+1}\\ &=\sum_{0}^{n} (x+1)^3H_{n+x+1}\delta x\\ &=[\frac{x^2(x+1)^2}{4}H_{n+x+1}]|_{0}^{n}-\sum_{0}^{n}\frac{(x+1)^2(x+2)^2}{4}\frac{1}{n+x+2}\delta x\\ &=\frac{n^2(n+1)^2}{4}H_{2n+1}-\sum_{0\leq k<n}\frac{(k+1)^2(k+2)^2}{4}\frac{1}{n+k+2}\\ &=\frac{n^2(n+1)^2}{4}H_{2n+1}\\ &\ \ \ \ \ -\frac{1}{4}\sum_{0\leq k<n}k^3-(n-4)k^2+(n^2-2n+5)k-n^3-n+2+\frac{n^2(n+1)^2}{n+k+2}\\ &=\frac{n^2(n+1)^2}{4}H_{2n+1}\\ &\ \ \ \ \ -\frac{1}{4}\sum_{1\leq k\leq n}(k-1)^3-(n-4)(k-1)^2+(n^2-2n+5)(k-1)-n^3-n+2+\frac{n^2(n+1)^2}{n+k+1}\\ &=\frac{n^2(n+1)^2}{4}(H_{2n+1}-\sum_{1\leq k\leq n}\frac{1}{n+k+1})+\frac{7n^4+2n^3-7n^2-2n}{48}\\ &=\frac{n^2(n+1)^2}{4}H_{n+1}+\frac{7n^4+2n^3-7n^2-2n}{48} \end{aligned}$$

3. Description of the Algorithm to Solve $S(n,m)$

To solve $S(n,m)=\sum_{k=1}^{n} k^mH_{n+k}$, we can find the function $v$ where $v(k,m)-v(k-1,m)=k^m$ first. The function $v$ is $v(n,m)=\sum_{k=1}^n k^m$.

As for the $v(n,m)$, we can calculate it using $v(1,m)$ to $v(n-1,m)$.

Because $n^m-(n-1)^{m}=\sum_{k=1}^{m}(-1)^{k-1}C_{m}^kn^{m-k}$, the $v(n,m)$ can be solved by item. Finally calculate all of them only use v(1,m) to v(n-1,m).

The result is $v(n,m)=\frac{1}{m+1}(n^{m+1}+\sum_{i=2}^{m+1}(-1)^iC_{m+1}^iv(n,m+1-i))$ .

Then, we can transfer $S(n,m)$ as followed:

$$\begin{aligned}S(n,m)&=\sum_{k=1}^{n} k^mH_{n+k}\\ &=\sum_{0\leq k< n} (k+1)^mH_{n+k+1}\\ &=\sum_{0}^{n} (x+1)^mH_{n+x+1}\delta x\\ &=[v(x,m)H_{n+x+1}]|_{0}^{n}-\sum_{0}^{n}v(x+1,m)\frac{1}{n+x+2}\delta x\\ &=v(n,m)H_{2n+1}-\sum_{1\leq k\leq n}v(k,m)\frac{1}{n+k+1}\\ \end{aligned}$$

The format of $\frac{1}{n+k+1}$ can be converted into $H_{n+k+1}-H_{n+k}$ as long as the $v(k,m)$ can be split out. In order to represent our answer using harmony number, we do polynomial division for $v(k,m)$ and $(n+k+1)$.

After the polynomial division, we can get polynomial $P_1(m), P_2(0)$ which satisfies the equation:

$$\frac{v(k,m)}{n+k+1}=P_1(m)+\frac{P_2(0)}{n+k+1}$$

$P(k)$ refers a polynomial whose order is less than or equal to $k$.

Finally,

$$\begin{aligned}\sum_{1\leq k\leq n}v(k,m)\frac{1}{n+k+1}&=\sum_{1\leq k\leq n}P_1(m)+P_2(0)\sum_{1\leq k\leq n}\frac{1}{n+k+1}\\&=\sum_{1\leq k\leq n}P_1(m)+P_2(0)(H_{2n+1}-H_{n+1})\end{aligned}$$

Assume that $P_1(m)=a_0k^0+a_1k^1+a_2k^2+\cdots+a_mk^m$, we can calculate using $v(n,1)$ to $v(n,m)$.

$$\begin{aligned}\sum_{1\leq k\leq n}P_1(m)&=\sum_{1\leq k\leq n}a_0k^0+a_1k^1+a_2k^2+\cdots+a_mk^m\\&=\sum_{i=0}^ma_i\sum_{1\leq k\leq n}k^i\\ &=\sum_{i=0}^ma_iv(n,i) \end{aligned}$$

which means $S(n,m)=(P_2(0)+v(n,m))H_{2n+1}-P_2(0)H_{n+1}+\sum_{i=0}^ma_iv(n,i)$ .