营业日志 2020.6.22 贝尔数的同余线性递推性质

今天粉兔同学问了一个问题：如何证明贝尔数的 Touchard's Congruence 性质： $$ B_{n+p} \equiv B_{n+1} + B_n \pmod p $$ 其中 $p$ 是质数，$B_n$ 是贝尔数。 为了证明这个问题，我们首先证明一个引理： **引理 1**：$\sum_k {p\brace k} x^k \equiv x + x^p \pmod p$。 **证明**：我们考虑多项式 $x^p = \sum_k {p\brace k} x^{\underline k}$，这是由下降幂转化得到的。而 $x^p \equiv x \pmod p$，$x^{\underline p} \equiv 0 \pmod p$，因此我们可以知道对于 $\sum_{k<p} {p\brace k} x^{\underline k} \equiv x \pmod p$，等式两边都是小于 $p$ 次的多项式，必然是对应相等的，而 ${p \brace p} = 1$ 显然。故 $\sum_k {p\brace k} x^k \equiv x + x^p \pmod p$ 得证。 接下来考虑这样一件事，记贝尔数的 EGF 是 $B(x) = \exp (\mathrm e^x - 1)$，那么 $B'(x) = B(x)\mathrm e^x$，我们考虑对 $B(x)$ 连续求导 $n$ 次，我们知道求导完必然是一个 $B^{(n)}(x) = B(x)\sum_k a_{n,k} \mathrm e^{kx}$ 的形式，归纳则有 $$ \begin{aligned} B^{(n+1)}(x) & = \left(B^{(n)}(x)\right)'\\ B(x)\sum_k a_{n+1,k} \mathrm e^{kx} &= \left(B(x)\sum_k a_{n,k} \mathrm e^{kx}\right)'\\ &= \sum_k a_{n,k} \left(B(x)\mathrm e^{kx}\right)'\\ &= \sum_k a_{n,k} \left(kB(x)\mathrm e^{kx} + B(x)\mathrm e^{(k+1)x}\right)\\ \sum_k a_{n+1,k} \mathrm e^{kx} &= \sum_k a_{n,k} \left(k\mathrm e^{kx} + \mathrm e^{(k+1)x}\right)\\ a_{n+1,k} &= ka_{n,k} + a_{n,k-1} \end{aligned} $$ 带入初值，我们容易得到 $$ B^{(n)}(x) = B(x) \sum_k {n\brace k} \mathrm e^{kx} $$ 令 $n=p$，有 $$ \begin{aligned} B^{(p)}(x) &= B(x) \sum_k {p\brace k} \mathrm e^{kx}\\ & \equiv B(x) (\mathrm e^x + \mathrm e^{px})\\ & \equiv B(x) (\mathrm e^x + 1)\\ & \equiv B'(x) + B(x)\\ B_{n+p} &\equiv B_{n+1} + B_n \end{aligned} $$ 故原问题得证。