等幂求和

等幂求和，即法乌尔哈贝尔公式（Faulhaber's formula），是指求幂数相同的变数之和$\sum_{i=1}^{n} x_i^m$。

## 常见公式

- 三角形数：$\sum^{n}_{i=1} i = \frac{n(n+1)}{2}$
- 正方形数：$\sum_{i=1}^{n} (2i - 1) = n^2$
- 调和级数：$\sum_{n=1}^k\,\frac{1}{n} \;=\; \ln k + \gamma + \varepsilon_k$

## 一般数列的等幂和

### 自然数等幂和

$$\sum_{i=1}^{n} i^{0} =n$$

$$\sum_{i=1}^{n} i^{1} = \frac{n(n+1)}{2} = \frac{1}{2}n^2 +\frac{1}{2} n$$

$\sum_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6} = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n$

$\sum_{i=1}^{n} i^{3} = \left[\frac{n(n+1)}{2}\right]^{2} = \frac{1}{4}n^4 + \frac{1}{2}n^3 + \frac{1}{4}n^2$

$\sum_{i=1}^{n} i^{4} = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30} = \frac{1}{5}n^5 + \frac{1}{2}n^4 + \frac{1}{3}n^3 - \frac{1}{30}n$

$\sum_{i=1}^{n} i^{5} = \frac{n^{2}(n+1)^{2}(2n^2+2n-1)}{12} = \frac{1}{6}n^6 + \frac{1}{2}n^5 + \frac{5}{12}n^4 - \frac{1}{12}n^2$

$\sum_{i=1}^{n} i^{6} = \frac{n(n+1)(2n+1)(3n^4+6n^3-3n+1)}{42} = \frac{1}{7}n^7 + \frac{1}{2}n^6 + \frac{1}{2}n^5 - \frac{1}{6}n^3 + \frac{1}{42}n$

$$\sum_{i=1}^{n} i^{7} = \frac{n^2(n+1)^2(3n^4+6n^3-n^2-4n+2)}{24} = \frac{1}{8}n^8 + \frac{1}{2}n^7 + \frac{7}{12}n^6 - \frac{7}{24}n^4 + \frac{1}{12}n^2$$

$$\sum_{i=1}^{n} i^{8} = \frac{n(n+1)(2n+1)(5n^6+15n^5+5n^4-15n^3-n^2+9n-3)}{90}=\frac{1}{9}n^9 + \frac{1}{2}n^8 + \frac{2}{3}n^7 - \frac{7}{15}n^5 + \frac{2}{9}n^3 - \frac{1}{30}n$$

$$\sum_{i=1}^{n} i^{9} = \frac{n^2(n+1)^2(n^2+n-1)(2n^4+4n^3-n^2-3n+3)}{20}=\frac{1}{10}n^{10}+\frac{1}{2}n^9+\frac{3}{4}n^8-\frac{7}{10}n^6+\frac{1}{2}n^4-\frac{3}{20}n^2$$

$\sum_{i=1}^{n} i^{10} = \frac{n(n+1)(2n+1)(n^2+n-1)(3n^6+9n^5+2n^4-11n^3+3n^2+10n-5)}{66}=\frac{1}{11}n^{11}+\frac{1}{2}n^{10}+\frac{5}{6}n^9-n^7+n^5-\frac{1}{2}n^3+\frac{5}{66}n$

$\sum_{i=0}^{n} i^{m-1} = \sum_{k=0}^m S_k^m n^k$，其中$S_0^m = 0$，$S_m^m = \frac{1}{m}$，当m−k为大于1的奇数时，$S_k^m = 0$。

$\sum_{i=0}^{n} i^m = {1\over{m+1}}\sum_{i=0}^m{m+1\choose{i}} B_i\, n^{m+1-i}$，其中$B_i$是伯努利数。

$\displaystyle \sum_{i=1}^n i^{m+1} = \sum_{k=0}^m L_k^m \binom{n+k+1}{m+2},\left(L_k^m = \sum_{r=0}^k (-1)^r \binom{m+2}{r} (k+1-r)^{m+1}\right)$

### 奇数等幂和与偶数等幂和

$$\sum_{i=1}^{n} (2i-1)^{0} =n$$

$$\sum_{i=1}^{n} (2i)^{0} =n$$

$$\sum_{i=1}^{n} (2i-1)^{1} =n^2$$

$$\sum_{i=1}^{n} (2i)^{1} = n(n+1)$$

$$\sum_{i=1}^{n} (2i-1)^{2} = \frac{n(2n-1)(2n+1)}{3}$$

$$\sum_{i=1}^{n} (2i)^{2} = \frac{2n(n+1)(2n+1)}{3}$$

$$\sum_{i=1}^{n} (2i-1)^{3} = n^2(2n^2-1)$$

$$\sum_{i=1}^{n} (2i)^{3} = 2 \left[ n(n+1) \right]^2$$

### 多项式求和

伯努利数也通用于等差数列的等幂和。

$$\sum_{i=1}^n (a_1+(i-1)d)^m = \frac{1}{m+1} \sum_{i=0}^m B_i d^{i-1} {m+1\choose i}(a_{n+1}^{m+1-i}-a_1^{m+1-i})$$

也可以利用帕斯卡矩阵，把多项式的和写成矩阵相乘。

$$\sum_{k=1}^n p(k)= \begin{pmatrix}C_n^1 & C_n^2 & \cdots & C_n^{m+1}\end{pmatrix} \begin{pmatrix} C_0^0 & 0 & \cdots & 0\\ -C_1^0 & C_1^1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ (-1)^mC_m^0 & (-1)^{m-1}C_m^1 & \cdots & C_m^m\\ \end{pmatrix} \begin{pmatrix}p(1)\\p(2)\\\vdots\\p(m+1)\end{pmatrix} =\sum_{j=1}^{m+1} C_{n}^{j}\Delta^{j-1}p(1)$$

其中$\Delta p(n)=p(n+1)-p(n)$

也可以将数列表达成组合数然后利用朱世杰恒等式求和。

$\sum_{i=1}^n \left(i^2-i\right)=2\sum_{i=1}^n C_i^2=2C_{n+1}^3$

## 多项式根的等幂和

$$\prod_{r=1}^n (x-x_r)=\sum_{r=0}^n a_r x^r=0,s_m=\sum_{r=1}^n x_r^m$$

### 牛顿公式

$s_m+a_1s_{m-1}+a_2s_{m-2}+...+a_{m-1}s_1+ma_m=0$

### 组合公式

$$s_m=\sum_{r_i=0}^{\lfloor \frac{m}{i} \rfloor} \frac{m(r_1+r_2+...+r_n -1)!}{r_1!r_2!...r_n!} \prod_{i=1}^n (-a_{n-i})^{r_i}$$

取$m=n=3$

$$\displaystyle x_1^3+x_2^3+x_3^3=\frac{3(3-1)!}{3!}(x_1+x_2+x_3)^3+\frac{3(1+1-1)!}{1!1!}(x_1+x_2+x_3)(-x_1x_2-x_1x_3-x_2x_3)+\frac{3(1-1)!}{1!}(x_1x_2x_3)$$

$$x_1^3+x_2^3+x_3^3=(x_1+x_2+x_3)^3-3(x_1+x_2+x_3)(x_1x_2+x_1x_3+x_2x_3)+3(x_1x_2x_3)$$

$$a_{n-m}=\sum_{r_i=0}^{\lfloor \frac{m}{i} \rfloor} \prod_{i=1}^m \frac{(-s_i)^{r_i}}{i^{r_i} r_i !}$$

取$m=n=3$

$$\displaystyle -x_1x_2x_3=\frac{1}{1^3 3!}(-x_1-x_2-x_3)^3 +\frac{1}{1^1 1! 2^1 1!}(-x_1-x_2-x_3)(-x_1^2-x_2^2-x_3^2) +\frac{1}{3^1 1!}(-x_1^3-x_2^3-x_3^3)$$

$$\displaystyle x_1x_2x_3=\frac{1}{6}(x_1+x_2+x_3)^3-\frac{1}{2}(x_1+x_2+x_3)(x_1^2+x_2^2+x_3^2)+\frac{1}{3}(x_1^3+x_2^3+x_3^3)$$