upd：请无视掉“常系数齐次线性递推”这个词……实际上只是单纯的可以递推……所以建议去 pdf 版 查看
本文的推法比较臃肿+有一些bug，完善的版本请访问：pdf 版
想法
在一类卷积递推式中，通常会转化成为生成函数来计算，在此只考虑二次卷积的形式
在本文中，只考虑如下生成函数的求法：
A(x)F^2(x)+B(x)F(x)+C(x)=0
其中 A(x),B(x),C(x) 是低阶多项式，F(x) 是待求序列的生成函数
通过二次方程的求根公式，可以得到：
F(x)=\frac{-B(x) \pm \sqrt{B^2(x)-4A(x)C(x)}}{2A(x)}
在确定完 \pm 取什么后，可以化作：
2A(x)F(x)=-B(x) \pm \sqrt{B^2(x)-4A(x)C(x)}
因此只需要考虑一类形如 \sqrt{A(x)} 的生成函数即可
基础
本文的理论基础为如下这个变形：
\begin{aligned} & F(x)=A(x)^{p} \\ \Rightarrow & F'(x)=pA(x)^{p-1}A'(x) \\ \Rightarrow & A(x)F'(x)=pA(x)^pA'(x) \\ \Rightarrow & A(x)F'(x)=pF(x)A'(x) \end{aligned}
其中 F(x),A(x) 为两个多项式
工具
考虑一类关于 F(x)=\sqrt{A(x)} 的生成函数，其中 A(x) 为某低阶多项式
则有：
F'(x)=\frac{A'(x)}{2\sqrt{A(x)}}=\frac{A'(x)}{2} G(x)
以及：
G'(x)=\left(\frac{1}{\sqrt{A(x)}}\right)'=-\frac{A'(x)}{2A(x)}G(x)
则有：
A'(x)G(x)=-2G'(x)A(x)
由于 A(x),A'(x) 均为低阶多项式，因此可以进行常系数齐次线性递推
于是可以推出 2F'(x)=A'(x)G(x)
即：
\sum_{n=0}^{\infty}2f_{n+1}(n+1)x^n=A'(x)G(x)
例题
已知某序列的生成函数为 F(x)=\frac{1-x-\sqrt{1-6x^+x^2}}{2x}，求其常系数齐次线性递推式
考虑到 1-x 和 2x 是没啥用的，所以相当于求 H(x)=\sqrt{1-6x+x^2} 的生成函数
令 G(x)=\frac{1}{H(x)}，通过套用上面的工具，可以得到：
(x-3)G(x)=-(1-6x+x^2)G'(x)
也就是：
(x-3)\sum_{n=0}^{\infty}g_nx^n=(-1+6x-x^2)\sum_{n=0}^{\infty}g_{n+1}(n+1)x^n
即：
\sum_{n=1}^{\infty}g_{n-1}x^n-\sum_{n=0}^{\infty}3g_nx^n=-\sum_{n=0}^{\infty}g_{n+1}(n+1)x^n+\sum_{n=1}^{\infty}6g_{n}nx^n-\sum_{n=2}^{\infty}g_{n-1}(n-1)x^n
那么有：
- 初值
g_0=G(0)=1
- 当 n=0 时
\begin{aligned} &-3g_0=-g_{0+1}(0+1) \\ \Rightarrow & -3g_0=-g_1 \\ \Rightarrow & g_1=3 \end{aligned}
- 当 n=1 时
\begin{aligned} &g_{1-1}x-3g_1x =-g_{1+1}(1+1)x+6g_11x-g_{1-1}(1-1)x\\ \Rightarrow & g_0-3g_1=-2g_2+6g_1 \\ \Rightarrow & 1-9=-2g_2+18 \\ \Rightarrow & g_2=13 \end{aligned}
- 当 n \ge 2 时
\begin{aligned} & \left(g_{n-1}-3g_n\right)x^n=\left(-g_{n+1}(n+1)+6g_nn-g_{n-1}(n-1) \right)x^n & \quad (n \ge 2) \\ \Rightarrow &g_{n-1}-3g_n=-g_{n+1}(n+1)+6g_nn-g_{n-1}(n-1) & \quad (n \ge 2) \\ \Rightarrow &g_{n-1}n-(3+6n)g_nn+g_{n+1}(n+1)=0 & \quad (n \ge 2) \\ \Rightarrow &g_{n+1}(n+1)=(3+6n)g_{n}-g_{n-1}n & \quad (n \ge 2) \\ \Rightarrow &g_{n}=\frac{(3+6(n-1))g_{n-1}-g_{n-2}(n-1)}{n} & \quad (n \ge 3) \end{aligned}
然后就可以来求 H(x) 了，由于：
\begin{cases} h_0=H(0)=1 \\ \sum_{n=0}^{\infty}2h_{n+1}(n+1)x^n=(2x-6)\sum_{n=0}^{\infty}g_nx^n=\sum_{n=1}^{\infty}2g_{n-1}x^n-\sum_{n=0}^{\infty}6g_nx^n \end{cases}
可以得到：
- 初值
\begin{cases} h_0=1 \\ 2h_{0+1}(0+1)=-6g_0 \Rightarrow 2h_1=-6 \Rightarrow h_1=-3 \end{cases}
- 当 n \ge 1 时：
\begin{aligned} &2h_{n+1}(n+1)=2g_{n-1}-6g_n \quad & (n \ge 1)\\ \Rightarrow &h_n=\frac{g_{n-2}-3g_{n-1}}{n} \quad & (n \ge 2) \end{aligned}
再回头看一眼 F(x) 的生成函数
由于：
2xF(x)=1-x-H(x)
也就是：
\begin{aligned} & 2x\sum_{n=0}^{\infty}f_nx^n=1-x-\sum_{n=0}^{\infty}h_nx^n \\ \Rightarrow &\sum_{n=1}^{\infty} 2f_{n-1}x^{n}=(1-h_0)-(h_1+1)x-\sum_{n=2}^{\infty}h_nx^n \end{aligned}
那么：
- 初值
\begin{aligned} &2f_0x=-(h_1+1)x \\ \Rightarrow & f_0=1 \end{aligned}
- 当 n \ge 2 时
\begin{aligned} &2f_{n-1}x^n=-h_nx^n & \quad (n \ge 2) \\ \Rightarrow & 2f_{n-1}=-h_n & \quad (n \ge 2) \\ \Rightarrow & f_{n}=-\frac{h_{n+1}}{2} & \quad (n \ge 1) \end{aligned}
习题
默慈金数
F(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}
卡特兰数
F(x)=\frac{1-\sqrt{1-4x}}{2}
斐波那契数
F(x)=\frac{x}{1-x-x^2}
参考文献
- 【生成函数及应用】ACdreamer
- 【迷思：寻找母函数运算的组合意义（一）】EntropyIncreaser
捐赠
我，作者，打钱(滑稽)