颓废记录

伯努利数

$\sum_{i=1}^n i^a$ 这种高次求和式显然没有一个通项式，但是可以通过递推来研究它。

对于上面的式子的求法，可以先凭空摆一个二项式定理：

$$(x-1)^{a+1}=\sum_{i=0}^{a+1}C_{a+1}^{i}(-1)^ix^{a+1-i} $$
对于右边式子的第一项 $x^{n+1}$，给它移到左边，就成了：

$$(x-1)^{a+1}-x^{a+1}=\sum_{i=1}^{a+1}C_{a+1}^{i}(-1)^ix^{a+1-i} $$
然后对左边的式子分别取 $x=1,2,3,…,n$：

$$(1-1)^{a+1}-1^{a+1}=\sum_{i=1}^{a+1}C_{a+1}^{i}(-1)^i1^{a+1-i} $$
$$(2-1)^{a+1}-2^{a+1}=\sum_{i=1}^{a+1}C_{a+1}^{i}(-1)^i2^{a+1-i} $$
$$…… $$
$$(n-1)^{a+1}-n^{a+1}=\sum_{i=1}^{a+1}C_{a+1}^{i}(-1)^in^{a+1-i} $$
并且全部相加，再用一下分配率：

$$1-n^{a+1}=\sum_{i=1}^nC_{a+1}^{i}(-1)^i\sum_{j=1}^nj^{a+1-i} $$
其中，右边式子的第一项中包含我们需要的 $\sum_{i=1}^n i^a$，所以把它拿出来，再对原来的等式变形一下，就得到了最终的式子。

在写它之前，先对刚才的目标式做一个格式化：令 $F(a)=\sum_{i=1}^ni^a$，则：

$$F(a) = \frac{(n+1)\left[(n+1)^a - 1\right] - \sum_{k=1}^{a-1}C_{k}^{a+1} F(k)}{a+1} $$
然后就可以进入正题，伯努利数。

刚才给出的式子在实际计算中显然过于复杂，我们不妨研究一下这其中蕴藏的递推关系。先给出 $F(a)$ 的前几项：

这个停更一下，先写点别的

斐波那契数列

这里说的并不是矩乘，而是关于这个数列的通项公式：

$$F_n=\dfrac{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}} $$
的证明方法。

相信学过数竞和物竞的 RedamancyLydic 一定熟知特征根，但是身为数学菜鸡的我丝毫不会证明特征根的正确性，于是来这里写一篇从零开始证明它（其实也是形如 $Aa_{x+2}=Ba_{x+1}+Ca_x$ 的所有递推式）的通项公式的文章。

矩阵证法我显然不会，所以这里使用生成函数,而且尽可能详细以便我这种菜鸡后期再来看的时候还能看懂。

首先斐波那契数列的普通生成函数为

$$G(x)=\sum_{n=0}^\infty F_n x^n $$
我们有递推公式

$$F_{n+2}=F_{n+1}+F_{n} $$
往上面乘点东西

$$F_{n+2}x^{n+2}=F_{n+1}x^{n+2}+F_nx^{n+2} $$
两边同时求和，得

$$\sum_{n=0}^\infty F_{n+2}x^{n+2}=\sum_{n=0}^\infty F_{n+1}x^{n+2}+\sum_{n=0}^\infty F_{n}x^{n+2} $$
左边的式子展开长这样

$$F_2x^2+F_3x^3+F_4x^4+\cdots $$
把它和

$$G(x)=F_0+F_1x+F_2x^2+F_3x^3+F_4x^4+\cdots $$
对比一下可以得到

$$\sum_{n=0}^\infty F_{n+2}x^{n+2}=G(x)-F_0-F_1x=G(x)-x $$
同理，等式右边第一个式子展开长这样

$$F_1x^2+F_2x^3+F_3x^4+\cdots $$
提一个 $x$ 出来

$$x(F_1x^1+F_2x^2+F_3x^3+F_4x^4+\cdots) $$
再去和 $G(x)$ 对比，可以得到

$$\sum_{n=0}^\infty F_{n+1}x^{n+2}=x(G(x)-F_0)=xG(x) $$
最后用同样的方法可以得到

$$\sum_{n=0}^\infty F_{n}x^{n+2}=x^2G(x) $$
然后我们可以得到一个关于 $G(x)$ 的方程

$$G(x)-x=xG(x)+x^2G(x) $$
把 $x$看成常数，解得

$$G(x)=\frac{x}{1-x-x^2} $$
于是我们得到等式

$$\frac{x}{1-x-x^2}=\sum_{n=0}^\infty F_n x^n $$
所以接下来的步骤就是把左边的式子展开成幂级数的形式。

这个式子不好看，所以我们需要对它在实数范围内因式分解。这个过程比较简单，所以直接给出最终结果

$$G(x)=\frac{-x}{(x-\varphi)(x-\mu)} $$
其中

$$\varphi=\frac{-1+\sqrt5}{2},\mu=\frac{-1-\sqrt5}{2} $$
把它裂项，即展开成

$$G(x)=\frac{A}{x-\varphi}+\frac{B}{x-\mu} $$
的形式，可以得到

$$A=\frac{-\varphi}{\sqrt5},B=\frac{\mu}{\sqrt5} $$
然后我们需要把这个式子变成幂级数的形式。

对于 $x\in (0,1)$，有

$$\sum_{n=0}^{\infty}x^n=1+x+x^2+\cdots=\frac{1-x^{n+1}}{1-x}=\frac{1}{1-x} $$
所以

$$\frac{a}{a-x}=\frac{a}{a(1-\frac{x}{a})}=\frac{1}{1-\frac{x}{a}}=\sum_{n=0}^{\infty}(\frac{x}{a})^n $$
对刚才得出的 $G(x)$ 进行带入，得到

$$G(x)=\frac{1}{\sqrt5}(\frac{\varphi}{\varphi-x}-\frac{\mu}{\mu-x}) $$
$$=\frac{1}{\sqrt5}(\sum_{n=0}^{\infty}(\frac{x}{\varphi})^n-\sum_{n=0}^{\infty}(\frac{x}{\mu})^n) $$
$$=\sum_{n=0}^{\infty}\frac{(\frac{1}{\varphi})^n-(\frac{1}{\mu})^n}{\sqrt5}x^n $$
又因为

$$\frac{1}{\varphi}=\frac{1+\sqrt5}{2},\frac{1}{\mu}=\frac{1-\sqrt5}{2} $$
故最终我们可以得到

$$G(x)=\sum_{n=0}^{\infty}\frac{(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n}{\sqrt5}x^n $$
把这个式子和 $G(x)$ 的定义式

$$G(x)=\sum_{n=0}^{\infty}F_nx^n $$
对比，就可以得到

$$F_n=\frac{(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n}{\sqrt5} $$
这就是斐波那契数列的通项公式了。

生成函数法求通项的关键在于对一个多项式进行形式幂级数展开。Heldivis 在下面列举了几种常用的转化：

$$\frac{1}{1-x}=\sum_{n=0}^\infty x^n $$
$$\frac{1}{(1-x)^a}=\sum_{n=0}^\infty C_{a+n-1}^a x^n $$
$$(x+1)^a=\sum_{n=0}^\infty C_{a}^{n}x^n $$
$$e^x=\sum_{n=0}^\infty \frac{x^n}{n!} $$
$$\ln(x+1)=\sum_{n=1}^\infty (-1)^{n-1}\frac{x^n}{n} $$
$$\frac{-\ln(1-x)}{1-x}=\sum_{n=1}^\infty (\sum_{j=1}^n\frac{1}{j})x^n $$
$$\frac{1-\sqrt{1-4x}}{2x}=\sum_{n=0}^{\infty}Cat_nx^n $$