这是为该文中的 整式递推函数复合后求系数 所撰的例题手稿。
Binomial Sum:
\[ans=\sum_{i=0}^{n}{n\choose i}i^k=\left[\frac{x^k}{k!}\right](e^x+1)^n\]
\[F(x):=(x+1)^n,\quad G(x+1):=F(x+1)\bmod x^{k+1}\]
\[\begin{aligned}(x+1)F'(x)&=nF(x)\\\Rightarrow(x+2)F'(x+1)&=nF(x+1)\\\Rightarrow (x+2)G'(x+1)&=nG(x+1)-2x^{k}[x^{k}]F'(x+1)\end{aligned}\]
Remark：可以直接考虑原等式中每一项系数是由哪些项贡献的，然后加加减减。
\[\because [x^k]F'(x+1)=[x^k]n(x+2)^{n-1}=n2^{n-1-k}{n-1\choose k}\]
\[\begin{aligned}\therefore(x+2)G'(x+1)&=nG(x+1)-2^{n-k}n{n-1\choose k}x^k\\\Rightarrow(x+1)G'(x)&=nG(x)-2^{n-k}n{n-1\choose k}(x-1)^k\end{aligned}\]
Remark：不要把 \(G(x)\) 写回闭形式，因为我们渴望递推。
\[\begin{aligned}g_i&:=[x^i]G(x)\quad(i\geqslant 0)\\\Rightarrow(i+1)g_{i+1}+ig_i&=ng_i-2^{n-k}n{n-1\choose k}(-1)^{k-i}{k\choose i}\end{aligned}\]
\[\begin{aligned}g_0=[x^0]G(x)&=[x^0]\sum_{i=0}^{k}(x-1)^i\cdot [z^i]G(z+1)\\&=\sum_{i=0}^{k}(-1)^i[z^i]F(z+1)\\&=\sum_{i=0}^{k}(-1)^i[z^i](z+2)^n\\&=\sum_{i=0}^{k}(-1)^i2^{n-i}{n\choose i}\end{aligned}\]
Remark：更一般地，因 \(F(x+1)\) 是微分有限的，只需递推求出 \([z^i]F(z+1)\) 。包括 \(G(x+c)\) 的 “微分有限” 方程中的修正项，也只需递推求解。
\[ans=\left[\frac{x^k}{k!}\right]G(e^x)\\=\left[\frac{x^k}{k!}\right]\sum_{i=0}^{k}g_ie^{ix}\\=\sum_{i=0}^{k}g_i\cdot i^k\]
\(U\) 群群友的提问：\(\sum_{i=0}^{n}(-1)^{n-i}{n\choose i}s_i=ds_n\;(n>0)\)，求 \(s_n\) 。给定 \(d\) 和 \(s_0\) 。
\[ans=\left[\frac{x^{n}}{n!}\right]\frac{s_0}{1-d^{-1}e^{-x}}\]
\[F(x):=\frac{s_0}{1-d^{-1}x},\quad G(x+1):=F(x+1)\bmod x^{n+1}\]
\[\begin{aligned}(1-d^{-1}x)F(x)&=s_0\\\Rightarrow [1-d^{-1}(x+1)]F(x+1)&=s_0\\\Rightarrow [1-d^{-1}(x+1)]G(x+1)&=s_0-d^{-1}x^{n+1}[x^n]F(x+1)\end{aligned}\]
Remark：不一定需要整式递推式，只要是可递推的都行。
\[\begin{aligned}\because[x^n]F(x+1)&=\frac{d^{-n}s_0}{(1-d^{-1})^{n+1}}\\\therefore[1-d^{-1}(x+1)]G(x+1)&=s_0-x^{n+1}\frac{d^{-n-1}s_0}{(1-d^{-1})^{n+1}}\end{aligned}\]
\[\begin{aligned}\lambda&:=\frac{d^{-n-1}s_0}{(1-d^{-1})^{n+1}}\\\Rightarrow (1-d^{-1}x)G(x)&=s_0-(x-1)^{n+1}\lambda\end{aligned}\]
\[\begin{aligned}g_i&:=[x^i]G(x)\quad(i\geqslant 0)\\g_i-d^{-1}g_{i-1}&=[i=0]s_0+(-1)^{n-i}\lambda\quad(i\geqslant 0)\end{aligned}\]
\[ans=\left[\frac{x^n}{n!}\right]G(e^{-x})=\sum_{i=0}^{n}(-1)^ig_i\cdot i^n\]
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
