营业日志 2020.5.9

> 一个在《具体数学》5.72 的等式，同时本人也很久以前在某“computer science cheatsheet”上看到过。 > 大致思想比较简单，但具体细节处有些吊诡。 欲证明 $$ \frac1{\sqrt{1-4x}} \left( \frac{1-\sqrt{1-4x}}{2x} \right)^m = \sum_n \binom{2n+m}{n}x^n $$ 定义二叉树方程 $F=x(1+F)^2$，可知原式 $$ \begin{aligned}&= \frac1 {\sqrt{1-4 \frac F{(1+F)^2}}} (1 + F)^m\\&= \frac{(1+F)^{m+1}}{1-F}\end{aligned} $$ 我们通过拉格朗日反演提取系数 $$ \begin{aligned}[x^n]\frac{(1+F)^{m+1}}{1-F} & = \frac 1n [w^{n-1}] \left( \frac{(1+w)^{m+1}}{1-w} \right )' (1+w)^{2n}\\&= \frac 1n [w^{n-1}] \frac{(1+w)^{m+2n} (2+m(1-w))}{(1-w)^2}\\&= \frac 1n [w^{n-1}] m\frac{(1+w)^{m+2n}}{(1-w)} + 2\frac{(1+w)^{m+2n}}{(1-w)^2}\\&= \frac 1n \sum_{k\le n-1} m\binom{m+2n}k + 2\binom{m+2n}k (n-k)\\&= \frac 1n \sum_{k\le n-1} \binom{m+2n}k (m+2n-2k)\\&= \frac 1n [w^{n-1}] \frac{(m+2n)(1+w)^{m+2n} - 2{(1+w)^{m+2n}}^\prime w}{1-w}\\&= \frac 1n [w^{n-1}] \frac{(m+2n)(1+w)^{m+2n} - 2(m+2n)(1+w)^{m+2n-1}w}{1-w}\\&= \frac 1n [w^{n-1}] \frac{(m+2n)(1+w)^{m+2n-1} (1+w-2w)}{1-w}\\&= \frac 1n [w^{n-1}] (m+2n)(1+w)^{m+2n-1}\\&= \frac 1n(m+2n)\binom{m+2n-1}{n-1}\\&= \binom{m+2n}n\end{aligned} $$