%EI 笔记： 一类特殊的线性求和

话不多说先%%%%%EI

对于给定的常数列\(a_i,i\in[0,n]\)

对于一些可以肉眼描述特征的多项式\(F(x)\)，以及一类特殊的\(G(x)\)

具体的，能够对于\(F(x)\)列出一条较为简单的微分方程，如\(F(x)=(1-x)F'(x)+H(x)\)

对于\(G(x)\)，容易求得\(\sum a_i[x^i]G^k(x)\)

则可以用下面的思路求得\(\sum a_i[x^i]F(G(x))\)

---

设\(c=G(0)\)，带入\(F(G(x))\)在\(c\)上的\(\text{Taylor}\)展开

\(\displaystyle F(G(x))=\sum_{i=0}^{\infty} F^{(i)}(c)\frac{(G(x)-c)^i}{i!}\)

由于\([x^0]G(x)-c=0\)，故仅\(i\leq n\)的项对于答案有贡献

我们求出的\(F^{(i)}(c)\)实际上由\(F(x+c)\)的前\(n\)项决定

也就是说，只要能够截取\(F(x+c)\)的前\(n\)项，设其为\(\mathscr F(x+c)=F(x+c)\mod x^{n+1}\)

那么我们再带入\(\displaystyle \mathscr F(G(x))=\sum_{i=0}^n\mathscr F_iG^i\)，根据前面提到的\(\sum a^i[x^i]G^k(x)\)就能求得答案

那么通过\(F(x+c)\)得到\(\mathscr F(x)\)，如果可以直接做就不谈

如果较复杂可以通过以下步骤

1.观察并列出\(F(x)\)的微分方程\(\sum p_i(x)F(x)=0\)，则同样有\(\sum p_i(x+c)F^{(i)}(x+c)=0\)

2.截取微分方程，得到同样系数的的方程

\(\sum p_i(x+c)\mathscr F^{(i)}(x+c)\)

然而由于\(\mathscr F^{(i)}(x+c)\)相较于\(F^{(i)}(x+c)\)缺少了部分项，设

\(\sum p_i(x+c)\mathscr F^{(i)}(x+c)=D(x)\)

如果\(D(x)\)较简洁，那么根据\(D(x)\)的形式，我们能够得到\(D(x-c)\)的展开

即\(\sum p_i(x)\mathscr F^{(i)}(x)=D(x-c)\)，此时再通过新的微分方程依次递推\(\mathscr F(x)\)的每一项即可

例子：

待补