一类通过生成函数求线性递推式的方法

upd：请无视掉“常系数齐次线性递推”这个词……实际上只是单纯的可以递推……所以建议去 [pdf 版](https://github.com/KingSann/useless-papers/blob/master/%E4%B8%80%E7%B1%BB%E9%80%9A%E8%BF%87%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0%E6%B1%82%E7%BA%BF%E6%80%A7%E9%80%92%E6%8E%A8%E5%BC%8F%E7%9A%84%E6%96%B9%E6%B3%95/%E4%B8%80%E7%B1%BB%E9%80%9A%E8%BF%87%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0%E6%B1%82%E7%BA%BF%E6%80%A7%E9%80%92%E6%8E%A8%E5%BC%8F%E7%9A%84%E6%96%B9%E6%B3%95.pdf) 查看 本文的推法比较臃肿+有一些bug，完善的版本请访问：[pdf 版](https://github.com/KingSann/useless-papers/blob/master/%E4%B8%80%E7%B1%BB%E9%80%9A%E8%BF%87%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0%E6%B1%82%E7%BA%BF%E6%80%A7%E9%80%92%E6%8E%A8%E5%BC%8F%E7%9A%84%E6%96%B9%E6%B3%95/%E4%B8%80%E7%B1%BB%E9%80%9A%E8%BF%87%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0%E6%B1%82%E7%BA%BF%E6%80%A7%E9%80%92%E6%8E%A8%E5%BC%8F%E7%9A%84%E6%96%B9%E6%B3%95.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$$ 那么有： 1. 初值 $$g_0=G(0)=1$$ 2. 当 $n=0$ 时 $$ \begin{aligned} &-3g_0=-g_{0+1}(0+1) \\ \Rightarrow & -3g_0=-g_1 \\ \Rightarrow & g_1=3 \end{aligned} $$ 3. 当 $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} $$ 4. 当 $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} $$ 可以得到： 1. 初值 $$ \begin{cases} h_0=1 \\ 2h_{0+1}(0+1)=-6g_0 \Rightarrow 2h_1=-6 \Rightarrow h_1=-3 \end{cases} $$ 2. 当 $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} $$ 那么： 1. 初值 $$ \begin{aligned} &2f_0x=-(h_1+1)x \\ \Rightarrow & f_0=1 \end{aligned} $$ 2. 当 $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](https://zhuanlan.zhihu.com/p/31457805) - [【迷思：寻找母函数运算的组合意义（一）】EntropyIncreaser](https://zhuanlan.zhihu.com/p/54318231) # 捐赠 ~~我，作者，打钱(滑稽)~~