用户: Cybcat/数学物理学家用的数学/一些生成函数技术

1第一例

最近我被问到这样一个问题:

例 1.1. 给定非负整数 $n$, 考虑$$\frac{(1+x{)}^{n+1}}{(1-x{)}^3}=\sum _{k=0}^{\infty }{a}_k{x}^k.$$求 $a_0+a_1+\cdots +a_n$.

注 1.2. 通过具体的数值计算, 我们能迅速找到, 对非负整数 $n$, 这个数列对应 OEIS $A055585$, 不过在那里我们并没有找到其生成函数的计算方式的细节, 让我们在这里进行详细的解读.

首先, 要计算展开中 $a_0+\cdots +a_n$ 的系数和, 我们应当考虑将 $\sum a_k{x}^k$ 乘上 $(1-x{)}^{-1}=1+x+x^2+\cdots$, 这样一来, 其系数变成 $a_0,a_0+a_1,a_0+a_1+a_2,\cdots$, 所以换言之, 我们现在要考虑的是下列表达式的 $x^n$ 系数, 也就是$$b_n:=\frac{(1+x{)}^{n+1}}{(1-x{)}^4}[x^n]=\frac{1}{2\pi i}{\int }_C\frac{(1+x{)}^{n+1}}{(1-x{)}^4}\frac{dx}{x^{n+1}}.$$其中 $C$ 是一个充分靠近 $0$ 的, 绕其一周的围道.

现在我们来证明 $b_n$ 符合四项递推 $(\lambda -2{)}^4$, 计算得到$$\begin{array}{rl}{b}_{n+4}-8b_{n+3}+24b_{n+2}-32b_{n+1}+16b_n& =\frac{1}{2\pi i}{\int }_C\frac{(1+1/x{)}^{n+1}}{(1-x{)}^4}\cdot (1+1/x-2{)}^{4}dx\\ & =\frac{1}{2\pi i}{\int }_C\frac{1}{x^4}\cdot (1+1/x{)}^{n+1}dx.\end{array}$$实际上, 当 $n=-4,-3,-2$ 时上述表达式取值 $1,-2,1$, 其余整数 $n$ 处均为 $0$ (不难检查 $n>-1$ 时不会产生 $1/x$ 项, 而 $n<-4$ 时 $b_{n+4}=\cdots =b_n=0$). 由此可知$$\begin{array}{rl}\sum _{n=0}^{\infty }{b}_n{y}^n& =\frac{1-2y+y^2}{(1-2y{)}^4}=\frac{1}{4}\frac{(1-2y+1{)}^2}{(1-2y{)}^4}\\ & =\frac{1}{4(1-2y{)}^2}+\frac{1}{2(1-2y{)}^3}+\frac{1}{4(1-2y{)}^4}.\end{array}$$这表明$$\begin{array}{r}{b}_n=2^n\left(\frac{1}{4}\left(\genfrac{}{}{0ex}{}{n+1}{1}\right)+\frac{1}{2}\left(\genfrac{}{}{0ex}{}{n+2}{2}\right)+\frac{1}{4}\left(\genfrac{}{}{0ex}{}{n+3}{3}\right)\right)=\frac{2^n}{24}(n+1)(n+3)(n+8).\end{array}$$

2第二例

例 2.1. 计算中心三项式数$$a_n:=[x^n](1+x+x^2{)}^n.$$

注 2.2. 仍然可以计算确定它就是 OEIS $A002426$. 但是让我们手动证明它具有我们想要的生成函数.

这次我们来演示直接计算留数. 仍然是考虑一个足够小的围道 $C$, 得到$$a_n=\frac{1}{2\pi i}{\int }_C\frac{(1+x+x^2{)}^n}{x^{n+1}}dx.$$这时取 $|y|$ 充分小 (依赖于 $C$ 的选取), 可以计算得到收敛的生成函数, 同时因为绝对收敛性还可以交换积分和求和的次序, 就得到$$\sum _{n=0}^{\infty }{a}_n{y}^n=\frac{1}{2\pi i}\sum _{n=0}^{\infty }{\int }_C\frac{(1+x+x^2{)}^n}{x^{n+1}}{y}^{n}dx=\frac{1}{2\pi i}{\int }_C\frac{dx}{x-(1+x+x^2)y}.$$注意到当 $|y|$ 充分小时, 分母的两根 $t_{\pm }:=(1-y\pm \sqrt{1-2y-3y^2})/2y$ 中其一趋于 $0$, 另一趋于 $\infty$. 所以计算留数可知, 在趋于 $0$ 的 $t_{-}$ 处的留数 $1/(y(t_{+}-t_{-}))=(1-2y-3y^2{)}^{-1/2}$ 就是最终的结果.

很明显这一计算可以被推广为 $[x^n](a+bx+c{x}^2{)}^n$, 最后会得到生成函数 $(1-2by+(b^2-4ac)y^2{)}^{-1/2}$. 即便有退化情况出现, 例如 $(a,b,c)=(1,2,1)$, 此时即研究 $[x^n](1+x{)}^{2n}=(\genfrac{}{}{0ex}{}{2n}{n})$ 的生成函数, 也能得到正确的 $(1-4y{)}^{-1/2}$.

3第三例

前一段时间看到一个怪东西. 假设我们用 $U(a,b)$ 表示一个均匀取 $[a,b]$ 间整数的随机变量. 记$$X_n:=U(0,U(1,\cdots ,U(n-1,n)\cdots )).$$求 $X_n$ 依分布收敛的极限.

实际上我们可以转换看法, 本质上说, $X_0=0$, $X_{n+1}:=U(0,1+X_n)$. 假设 $X_n$ 的生成函数为 $f_n(x)$, 即若 $p_{nk}:=\mathbb{P}[X_n=k]$, 则定义 $f_n(x):={\sum }_k{p}_{nk}{x}^k$. 现在对于 $X_n=k$ 的情形, 此时 $X_{n+1}$ 将会是 $0,\cdots ,k+1$ 的均匀分布. 所以从生成函数上看, $f_n$ 的项 $x^k$, 它会被分摊到下一个生成函数 $f_{n+1}$ 的 $\frac{1}{k+2}(x^0+x^1+\cdots +x^{k+1})=\frac{1}{k+2}\frac{1-x^{k+2}}{1-x}$, 所以$$f_{n+1}(x)=\frac{{\int }_x^{1}t{f}_n(t)dt}{1-x}.$$由泛函技术我们知道 $f_n$ 的极限函数存在唯一. 对于上述算子作用下稳定的 $f(x)$, 其满足微分方程$$\frac{d}{dx}\left((1-x)f(x)\right)+xf(x)=0⟹(1-x)(f^{\prime }(x)-f(x))=0.$$由此我们知道 $f(x)=c{e}^x$, 结合概率和为 $1$ 的条件 $f(1)=1$ 就得到 $c=e^{-1}$, 所以这意味着最后的极限分布 $X$ 为 Poisson 分布 $\mathrm{Poi}(1)$.

另外, 即便从概率论视角, 这个方法也有其道理, 我们可以通过研究分布的特征函数来代替生成函数. 此时我们看到了一个 Markov 过程, 它的收敛性由一些概率论事实保证. 从这个角度求它的平稳分布就应当满足: $$\{\begin{array}{l}{p}_0=\frac{p_0}{2}+\frac{p_1}{3}+\frac{p_2}{4}+\cdots \\ p_1=\frac{p_0}{2}+\frac{p_1}{3}+\frac{p_2}{4}+\cdots \\ p_2=\frac{p_1}{3}+\frac{p_2}{4}+\frac{p_3}{5}+\cdots \\ p_3=\frac{p_2}{4}+\frac{p_3}{5}+\frac{p_4}{6}+\cdots \\ \cdots \end{array}⟹\{\begin{array}{l}{p}_0-p_1=0\\ p_1-p_2=\frac{p_0}{2}\\ p_2-p_3=\frac{p_1}{3}\\ p_3-p_4=\frac{p_2}{4}\\ \cdots \end{array}.$$由此解出 $p_n=p_0/n!$ 并不困难.

4第四例

例 4.1. 计算下面的极限: $$\underset{n\to +\infty }{\lim }\frac{1}{\log \log n}\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)(-1{)}^k\log k.$$

简单观察问题, 会发现它要计算的东西是 $\log$ 序列不断差分的结果, 但是真的这样去研究问题就上当了, 计算它最有效的方法就是使用类似生成函数的看法. 这种形状东西肯定可以被写成好看的积分. 注意到:

$${\int }_0^1\sum _{m=1}^{k-1}\frac{1}{x+m}dx=\sum _{m=1}^{k-1}(\log (m+1)-\log m)=\log k.$$

这样我们就能把原问题中的求和写出来

$$\begin{array}{rl}\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)(-1{)}^k\log k& ={\int }_0^1\sum _{m=1}^{n-1}\frac{1}{x+m}\sum _{k=m+1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)(-1{)}^{k}dx\\ & ={\int }_0^1\sum _{m=1}^{n-1}\frac{(-1{)}^{m-1}}{x+m}\left(\genfrac{}{}{0ex}{}{n-1}{m}\right)dx\\ & ={\int }_0^1\left(\frac{1}{x}-\frac{(n-1)!}{x(x+1)\cdots (x+n-1)}\right)dx.\end{array}$$

这里最后一个等号可以通过裂项看出来, 总而言之这个积分现在可以被整理为$${\int }_0^1\left(\frac{1}{x}-\frac{\Gamma (n)\Gamma (x)}{\Gamma (n+x)}\right)dx={\int }_0^1\frac{1}{x}\left(1-\frac{\Gamma (n)\Gamma (x+1)}{\Gamma (n+x)}\right)dx.$$然后利用在 $0<x<1$ 时 $\Gamma$ 函数的展开: $$\Gamma (x+1)=1-\gamma x+\frac{\zeta (2)+{\gamma }^2}{2}{x}^2+O(x^3).$$还有 $n$ 很大时如下的展开: $$\frac{\Gamma (n)}{\Gamma (n+x)}=n^{-x}\left(1+O\left(\frac{1}{n}\right)\right).$$最后结合积分表达式$${\int }_0^1\frac{1-n^{-x}}{x}dx=\log \log n+\gamma +O\left(\frac{1}{n}\right),$$我们实则可以得到如下的渐近表达式$$\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)(-1{)}^k\log k=\log \log n+\gamma +\frac{\gamma }{\log n}-\frac{{\pi }^2+6{\gamma }^2}{12{\log }^{2}n}+O\left(\frac{1}{{\log }^{3}n}\right).$$

本例的技术来自

Mellin transforms and asymptotics: Finite differences and Rice’s integrals. by Philippe Flajolet & Robert Sedgewick.