调和级数求和问题

数学星空

记\(H_n=\sum_{k=1}^n \frac{1}{k}, S_m(n)=\sum_{k=1}^n \frac{1}{k^m}\),

求证下面公式(摘录<拉马努金笔记本Ｉ>)

1.\(\sum_{k=1}^n H_k=(n+1)H_n-n\)

2.\(\sum_{k=1}^n H_k^2=(n+1)H_n^2-(2n+1)H_n+2n\)

3.\(\sum_{k=1}^n H_k^3=(n+1)H_n^3-\frac{3(2n+1)H_n^2}{2}+3(2n+1)H_n-6n+\frac{1}{2}S_2(n)\)

进一步给出下面和式的计算公式

4.\(\sum_{k=1}^n H_k^4\)

5.\(\sum_{k=1}^n H_k^5\)

6.\(\sum_{k=1}^n H_k^6\)

数学星空

以下的证明基于下面的阿贝尔变换：

\(\sum_{k=1}^n a_kb_k=S_n b_n-\sum_{k=1}^{n-1} S_k(b_{k+1}-b_k)\),其中\(S_n=\sum_{k=1}^n a_n\)

1.\(\sum_{k=1}^n H_k=nH_n-\sum_{k=1}^{n-1} (1-\frac{1}{k+1})=(n+1)H_n-n\)

2.\(\sum_{k=1}^n H_k^2=(n+1)H_n^2-nH_n-\sum_{k=1}^{n-1} (H_k-\frac{k}{k+1})=(n+1)H_n^2-nH_n-((n+1)H_n-2n)=(n+1)H_n^2-(2n+1)H_n+2n\)

3.\(\sum_{k=1}^n H_k^3=(n+1)H_n^3-(2n+1)H_n^2+2nH_n-\sum_{k=1}^{n-1} (H_k^2-2H_k+\frac{H_k}{k+1}+2-\frac{2}{k+1})\)

                     \(=(n+1)H_n^3-(2n+1)H_n^2+2nH_n-(nH_n^2-(4n+3)H_n+6n+\sum_{k=1}^{n-1}\frac{H_k}{k+1})\)

                     \(=(n+1)H_n^3-(3n+\frac{3}{2})H_n^2+(6n+3)H_n-6n+\frac{1}{2}S_2(n)\)

注：\(\sum_{k=1}^{n-1}\frac{H_k}{k+1}＝\frac{1}{2}(H_n^2-S_2(n))\)

对于更高阶的求和问题；

4.\(\sum_{k=1}^n H_k^4=(n+1)H_n^4-(3n+\frac{3}{2})H_n^3+(6n+3)H_n^2-6nH_n+\frac{1}{2}S_2(n)H_n-\sum_{k=1}^{n-1} (H_k^3-3H_k^2+\frac{3H_k^2}{2(k+1)}+6H_k-\frac{3H_k}{k+1}-6+\frac{6}{k+1}+\frac{S_2(k)}{2(k+1)})\)

   其中：\(\sum_{k=1}^{n-1} (H_k^3-3H_k^2+\frac{3H_k^2}{2(k+1)}+6H_k-\frac{3H_k}{k+1}-6+\frac{6}{k+1}+\frac{S_2(k)}{2(k+1)})＝nH_n^3-(6n+\frac{3}{2})H_n^2+(18n+12)H_n-(24n-\frac{1}{2}S_2(n))+\sum_{k=1}^{n-1} (\frac{3H_k^2}{2(k+1)}-\frac{3H_k}{k+1}+\frac{S_2(k)}{2(k+1)})\)

   剩下的问题如何求解：\(\sum_{k=1}^{n-1} (\frac{H_k^2}{k+1})\)及\(\sum_{k=1}^{n-1} \frac{S_2(k)}{k+1}\)

数学星空

看来计算下面类型的和式行不通，有谁能估计出相关结果(尽可能精确)

1.\(\sum_{k=1}^n \frac{H_k^p}{k+1}\)

2.\(\sum_{k=1}^n \frac{S_m(k)^p}{k+1}\)

3.\(\sum_{k=1}^n \frac{S_m(k)^p}{k^q}\)

其中\(m,n,p,q\)为已知正整数

kastin

上面给出的公式还是依赖于 `H_n` 和 `S_m(n)`，如果不能给出这两个的估计式，找出这些公式又有什么用处呢？

kastin

之前一段时间研究过调和级数的数值计算，手头有这样的资料，不知是否对你有用：
$$H_n\approx \ln n + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \frac{1}{252n^6} + \gamma$$
其中，欧拉常数 `\gamma = 0.57721566490153286060651209402431\dots`
上面公式误差项为 `\D O(\frac{1}{240n^8})`，当 `n\geqslant 100`时，能保证小数点后精确位数为16位。

还有$$S_{-1}(n)=\ln 2+\frac{(-1)^n}{2}\left(\psi(\frac{n}{2}+\frac{1}{2})-\psi(\frac{n}{2}+1)\right)$$其中Digamma函数定义为 `\psi(x)=\D \frac{\dif \ln\Gamma(x)}{\dif x}`.

$$S_{m}(n)\approx \zeta (m)+n^{-m}\left(\frac{1}{2}-\frac{n}{m-1}-\frac{m}{12 n}+\frac{m(m+1) (m+2) }{720 n^3}-\frac{m (m+1) (m+2) (m+3) (m+4)}{30240 n^5}+\frac{m (m+1) (m+2) (m+3) (m+4) (m+5) (m+6) }{1209600 n^7}\right)++O\left(\frac{1}{n^m n^9}\right),\;(m>1,m\in\ZZ)$$其中，`\zeta(z)` 为黎曼函数.

mathematica

调和级数的问题应该比较难吧

baixinbs

前段时间还遇到用图论中用调和级数设计算法的例子。如这个文章S. Guha and S. Khuller, “Approximation Algorithms for Connected Dominating Sets,” Algorithmica, vol. 20, pp. 374-387, Apr. 1998

Buffalo

那些求和式不一定有简单闭形式，但是如果只想求它的渐近式那就是简单的体力活了。
假设已经知道$f(n)$的渐近式为$f(n)~\sum_{i=0}^{\infty}u_i(n)$，可以简单地用欧拉-马克劳林公式求得$S(n)=\sum_{k=1}^{n}f(k)~\sum_{i=0}^{\infty}\sum_{k=1}^{n}u_i(k)$的渐近式。也可以对差分方程$S(n)-S(n-1)=f(n)$用待定系数法逐次展开。
比如这里的$H_n~\ln n+\gamma+\sum_{i=1}^{\infty}\frac{c_i}{n^i}$，因此$\frac{H_n^p}{n+a}~\sum_{i=0}^{p}(\ln n+\gamma)^i\sum_{j=0}^{\infty}\frac{c_{ij}(a)}{n^{j+1}}$，$\sum_{k=1}^{n}\frac{H_k^p}{k+a}~\sum_{i=0}^{p+1}(\ln n+\gamma)^i\sum_{j=0}^{\infty}\frac{d_{ij}(a)}{n^j}$。

Buffalo

对于本题要解决的$\sum_{k=1}^{n}H_k^p$问题，容易求得前面几项为$n\sum_{i=0}^{p}(-1)^{p-i}\frac{p!}{i!}(\ln n+\gamma)^{i}+(\ln n+\gamma)^{p}+d+O(\frac{(\ln n)^p}{n})$。这就引导我们去找到合适的表达式：由于$H_n~\ln n+\gamma+\frac{1}{2n}$，代入到上面的渐近式，立刻得到$\sum_{k=1}^{n}H_k^p~(n+1)H_n^p+(n+\frac{1}{2})\sum_{i=0}^{p-1}(-1)^{p-i}\frac{p!}{i!}H_n^i+d'+O(\frac{(\ln n)^p}{n})$。
现在剩下最后一个问题：找到收敛数列$\sum_{k=1}^{n}H_k^p-[(n+1)H_n^p+(n+\frac{1}{2})\sum_{i=0}^{p-1}(-1)^{p-i}\frac{p!}{i!}H_n^i]$的表达式。
令$D_n=\sum_{k=1}^{n}H_k^p-[(n+1)H_n^p+(n+\frac{1}{2})\sum_{i=0}^{p-1}(-1)^{p-i}\frac{p!}{i!}H_n^i]$，直接计算可得$D_n-D_{n-1}=-\sum_{j=2}^{p-1}\frac{(j-1)(-1)^{j}p!}{2n^j(j+1)!}\sum_{i=0}^{p-1-j}\frac{(-1)^{i}H_n^i}{i!}$。这就是为什么$p\ge4$时出求不出求和的闭形式结果，因为这时需要求出$\frac{H_k^p}{k^q}$的和。

Buffalo

由上面的分析知道，只要对$q\ge2$，$p\le P-3$能求出$\sum_{k=1}^{n}\frac{H_k^p}{k^q}$的闭形式就能求出$\sum_{k=1}^{n}H_k^{P}$的闭形式。
由积分方法给出的前几项，可以假设$\sum_{k=1}^{n}\frac{H_k^p}{k^q}=L+\sum_{i=0}^{p}H_n^{p-i}f_i(n)$，$L=\sum_{k=1}^{\infty}\frac{H_k^p}{k^q}$，于是必须有$\sum_{i=0}^{p}H_n^{p-i}f_i(n)-\sum_{i=0}^{p}(H_n-\frac{1}{n})^{p-i}f_i(n-1)=frac{H_n^p}{n^q}$，把这个方程看成$H_n$的代数方程，就给出了关于系数$f_i(n)$的递推一阶线性差分方程组：$f_0(n)-f_1(n-1)=\frac{1}{n^q}$，以及对$1\le i \le p $，$f_i(n)-f_i(n-1)=\sum_{j=1}^{i}(-1)^j\frac{(p-i+j)!}{(p-i)!j!n^j}f_{i-j}(n-1)$，$f_0(n)=S_q(n)-\zeta(q)$，……。