？
Nygglatho
·
·
题解
省流：
f_i=\sum\limits_{j}f_jf_{i-j-1}\\
g_i=\sum\limits_{j}2f_jg_{i-j-1}
首先有：
\begin{aligned}
F(x)&=\sum\limits_{i\ge 0}f_ix^i\\
&=1+\sum\limits_{i\ge 1}f_ix^i\\
&=1+\sum\limits_{i\ge 1}\sum\limits_{0\le j<i}f_jx^jf_{i-j-1}x^{i-j-1}x\\
&=1+x\sum\limits_{i\ge 0}\sum\limits_{0\le j\le i}f_jx^jf_{i-j}x^{i-j}\qquad\qquad i\gets i-1，提出\ x\\
&=1+x\sum\limits_{i\ge 0}\sum\limits_{0\le j\le i}f_jx^if_{i-j}\\
&=1+x\sum\limits_{i\ge 0}x^i\sum\limits_{0\le j\le i}f_jf_{i-j}\\
&=1+x[F(x)]^2
\end{aligned}
此时我们有：
\begin{aligned}
F(x)&=1+x[F(x)]^2\\
xF(x)^2-F(x)+1&=0\\
F(x)&=\dfrac{1\pm \sqrt{1-4x}}{2x}
\end{aligned}
取 F(x)=\dfrac{1-\sqrt{1-4x}}{2x}.
同样的，可以得到 G(x)：
\begin{aligned}
G(x)&=\sum\limits_{i\ge 0}g_ix^i\\
&=x+\sum\limits_{i\ge 2} \sum\limits_{0\le j<i}2f_jx^jg_{i-j-1}x^{i-j-1}x\\
&=x+2x\sum\limits_{i\ge 0}\sum\limits_{0\le j\le i}f_jx^jg_{i-j}x^{i-j}\\
&=x+2x\sum\limits_{i\ge 0}\sum\limits_{0\le j\le i}f_jx^ig_{i-j}\\
&=x+2x\sum\limits_{i\ge 0}x^i\sum\limits_{0\le j\le i}f_jg_{i-j}\\
&=x+2xF(x)G(x)
\end{aligned}
有：
\begin{aligned}
G(x)&=x+2xF(x)G(x)\\
G(x)-2xF(x)G(x)&=x\\
(1-2xF(x))G(x)&=x\\
G(x)&=\dfrac{x}{1-2xF(x)}\\
\end{aligned}
代入 F(x) 有：
\begin{aligned}
G(x)&=\dfrac{x}{1-2x\dfrac{1-\sqrt{1-4x}}{2x}}\\
&=\dfrac{x}{1-(1-\sqrt{1-4x})}\\
&=\dfrac{x}{\sqrt{1-4x}}\\
&=x(1-4x)^{-\frac{1}{2}}
\end{aligned}
考虑展开. 有：
\begin{aligned}
\dfrac{-1}{2}^{\underline n}&=\dfrac{-1}{2}\times\dfrac{-3}{2}\times\cdots\\
&=\prod\limits_{i=0}^{n-1}\dfrac{-1-2i}{2}\\
&=\prod\limits_{i=0}^{n-1}(-1)\left(\dfrac{2i+1}{2}\right)\\
&=(-1)^n\prod\limits_{i=0}^{n-1}\left(\dfrac{2i+1}{2}\right)\\
&=(-1)^n\dfrac{1}{2^n}\prod\limits_{i=0}^{n-1}(2i+1)\\
&=(-1)^n\dfrac{1}{2^n}\prod\limits_{i=1}^{n}(2i-1)\\
&=(-1)^n\dfrac{1}{2^n}(2n-1)!!\\
&=(-1)^n\dfrac{1}{2^n}\dfrac{(2n)!}{(2n)!!}\\
&=(-1)^n\dfrac{1}{2^n}\dfrac{(2n)!}{2^nn!}\\
\end{aligned}
根据牛顿二项式定理，代入，有：
\begin{aligned}
G(x)&=x\sum\limits_{i\ge 0}\left(\dfrac{-1}{2}\right)^{\underline i}\dfrac{1}{i!}(-4x)^i\\
&=x\sum\limits_{i\ge 0}(-1)^i(-1)^i\dfrac{1}{2^i}\dfrac{(2i)!}{2^ii!}\dfrac{1}{i!}4^ix^i\\
&=x\sum\limits_{i\ge 0}\dfrac{(2i)!}{(i!)^2}x^i\\
&=\sum\limits_{i\ge 0}\dfrac{(2i)!}{(i!)^2}x^{i+1}\\
&=\sum\limits_{i\ge 1}\binom{2i}{i}x^i
\end{aligned}
于是得出 G(x).
关于 F(x)，差别不大，不想推了.