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

2019-01-20 22:00:28


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$$

那么有:

  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}$$

参考文献

捐赠

我,作者,打钱(滑稽)