自然数幂和小结

开个小坑，介绍自然数幂和（等幂求和）问题以及相关算法。

等幂求和问题

等幂求和问题（Faulhaber’s formula）¹ 指计算多项式

$$f_k(n) = \sum_{i=0}^n i^k = 0^k+1^k+2^k+\cdots +n^k$$

的值。

对于$k$较小的情况：

• 当$k=1$时有$f_1(n) = \frac{n(n+1)}{2}$。
• 当$k=2$时有$f_2(n) = \frac{n(n+1)(2n+1)}{6}$。

插值法

使用插值法计算的主要方式是，先利用多项式的$O(k)$个点值得出该多项式的表示，然后用此表示来计算点值。

拉格朗日插值法

如果只是单点求值，那么可以直接利用拉格朗日多项式

$$\sum_{i}y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}$$

来计算。单次求值的时间复杂度是$O(k^2)$。

如果取$x_i=i$，那么在模意义下可以使用阶乘及其逆元来进一步优化，做到$O(k)$的时间计算点值。

如果要得到$F_k$的系数表示，那么暴力模拟多项式展开的过程是$O(k^3)$的。

使用缺一背包的方式分治计算可以做到$O(k^2\log_2k)$。

差分法

取$x_i = i$（$0\le i\le k+1$）共$k+2$个点，然后将其差分。

具体地，设$d_j(i) = d_{j-1}(i)-d_{j-1}(i-1)$，$j$表示差分的次数，$d_0(i) = i$。那么有

$$F_k(n) = \sum_{i=0}^{k+1} \binom{n}{i} d_i(i)$$

这实际上是求出了$F_k(n)$的下降幂表示。利用斯特林数的变换：

$$n^{\underline{k}} = \sum_{i = 0}^ks(k, i)(-1)^{k-i}n^i$$

我们也可以在$O(k^2)$的时间内将其转化为常幂系数表示。

代码

二项式定理

利用二项式定理也可以计算等幂求和，其主要思想是通过差分、裂项等方法构造等式，推导递推式。首先

$$(x+1)^k = \sum_{i =0}^k\binom{k}{i}x^i$$

通过移项构造一个差分形式：

$$(x+1)^k-x^k = \sum_{i=0}^{k-1}\binom{k}{i}x^i$$

这样就能得到

$$\begin{aligned} n^k &= \sum_{i=0}^{n-1}(i+1)^k-i^k\\ &= \sum_{i=0}^{n-1}\sum_{j=0}^{k-1}\binom{k}{j}i^j\\ &= \sum_{j=0}^{k-1}\binom{k}{j}F_j(n-1) \end{aligned}$$

然后我们再次移项得到$F_{k-1}$的递推式：

$$F_{k-1}(n-1) = \frac{n^k-\sum_{j=0}^{k-2}\binom{k}{j}F_j(n-1)}{k}$$

所以整理一下得到

$$F_{k}(n) = \frac{n^{k+1}-\sum_{j=0}^{k-1}\binom{k+1}{j}F_j(n)}{k+1}$$

斯特林数

使用斯特林数计算等幂求和的要点在于构造递归式。由下降幂转通常幂的公式：

$$n^{\underline{m}}=\sum_{i=0}^m(-1)^{m-i}s(m,i)n^i$$

移项得到

$$n^m=n^{\underline{m}}-\sum_{i=0}^{m-1}(-1)^{m-i}s(m,i)n^i$$

所以我们把这个公式代入等幂求和公式得到

$$\begin{aligned} F_k(n)&=\sum_{i=1}^n\left(i^{\underline{k}} -\sum_{j=0}^{k-1}(-1)^{k-j}s(k,j)i^j \right)\\ &=k!\sum_{i=1}^n\binom{i}{k}-\sum_{j=0}^{k-1}(-1)^{k-j}s(k,j)F_j(n)\\ &=k!\binom{n+1}{k+1}-\sum_{j=0}^{k-1}(-1)^{k-j}s(k,j)F_j(n) \end{aligned}$$

这样我们就可以递归求解了。

伯努利数

等幂求和也可以借助伯努利数²相关的知识计算。伯努利数序列并不具有直观含义，但其指数生成函数（EGF）为

$$\hat{B}(x) = \frac{x}{e^x-1} = \sum_{i\ge 0}B_i \frac{x^i}{i!}$$

为了推导等幂求和的系数表示，我们先介绍伯努利多项式的定义：

$$\beta_n(z)= \sum_{i=0}^n\binom{n}{i}B_iz^{n-i}$$

伯努利多项式实际上是一个序列$\beta_0(z), \beta_1(z), \cdots$，这个序列的每一个元素都是个多项式。

因此我们可以求出这个序列的指数生成函数（多项式序列的生成函数）：

$$\hat{\mathbf{B}}_z(x) = \sum_{i\ge 0}\beta_i(z) \frac{x^i}{i!}$$

把$z$写成下标是因为这个生成函数中$x$作为主要的占位符。接下来我们推导其封闭形式：

$$\begin{aligned} \hat{\mathbf{B}}_z(x) = & \sum_{i\ge 0}\beta_i(z) \frac{x^i}{i!}\\ = & \sum_{i\ge 0} \frac{x^i}{i!} \sum_{j=0}^i\binom{i}{j}B_jz^{i-j} \\ = & \sum_{i\ge 0} \sum_{j=0}^i \frac{B_jx^j}{j!} \frac{z^{i-j}x^{i-j}}{(i-j)!} \\ = & \frac{x}{e^x-1}e^{zx} \end{aligned}$$

接下来我们将其差分：

$$\hat{\mathbf{B}}_{z+1}(x) - \hat{\mathbf{B}}_z(x) = \frac{x}{e^x-1}e^{(z+1)x} - \frac{x}{e^x-1}e^{zx} = xe^{zx}$$

这对应的是序列$\beta_i(z+1)-\beta_i(z)$的 EGF。将其展开得到

$$xe^{zx} = \sum_{i\ge 0} \frac{z^ix^{i+1}}{i!} = \sum_{i\ge 0} z^i(i+1) \frac{x^{i+1}}{(i+1)!}$$

因此我们得到$\beta_{i+1}(z+1)-\beta_{i+1}(z) = z^i(i+1)$，即

$$z^i = \frac{\beta_{i+1}(z+1)-\beta_{i+1}(z)}{i+1}$$

我们将$z^i$表示为了差分的形式，因此我们可以裂项相消：

$$\begin{aligned} \sum_{i=0}^n i^k &= \frac{1}{k+1}\sum_{i=0}^n \beta_{k+1}(i+1)-\beta_{k+1}(i)\\ &= \frac{\beta_{k+1}(n+1) - \beta_{k+1}(0)}{k+1} \\ &= \sum_{i=0}^{k+1}\binom{k+1}{i}B_i(n+1)^{k+1-i} - B_{k+1} \\ &= \sum_{i=0}^{k}\binom{k+1}{i}B_i(n+1)^{k+1-i} \end{aligned}$$

这样我们就直接得到了$F_k(n)$的系数表示。

¹. https://en.wikipedia.org/wiki/Faulhaber%27s_formula ↩

². https://zh.wikipedia.org/zh-cn/%E4%BC%AF%E5%8A%AA%E5%88%A9%E6%95%B0 ↩