生成函数来全秒了！

· · 个人记录

前情提要：范德蒙德卷积做一半！

组合意义天地灭，代数推导保平安。

不废话，就写式子。

\sum_{n=0}^\infty\sum_{m=0}^nx^ny^m\sum_{i=m}^n\binom{p+i-1}{i}\binom{q+n-i-1}{n-i} =\sum_{n=0}^\infty x^n\sum_{i=0}^n\binom{p+i-1}{i}\binom{q+n-i-1}{n-i}\frac{1-y^{i+1}}{1-y} =\frac{1}{1-y}\sum_{i=0}^\infty(1-y^{i+1})\binom{p+i-1}{i}\sum_{n=0}^\infty\binom{q+n-1}{n}x^{n+i} =\frac{1}{1-y}\sum_{i=0}^\infty(1-y^{i+1})\binom{p+i-1}{i}\frac{x^i}{(1-x)^q} =\frac{1}{(1-y)(1-x)^q}\left(\frac{1}{(1-x)^p}-\frac{y}{(1-xy)^p} \right)

另一方面

\sum_{n=0}^\infty\sum_{m=0}^n x^ny^m\sum_{i=1}^p\binom{i+m-2}{m-1}\binom{n-m+p+q-i}{n-m} =\sum_{i=1}^p\sum_{m=0}^\infty y^m\binom{i+m-2}{m-1}\sum_{n=0}^\infty x^{n+m}\binom{n+p+q-i}{n} =\sum_{i=1}^p\sum_{m=0}^\infty y^m\binom{i+m-2}{m-1}\frac{x^m}{(1-x)^{p+q-i+1}} =\sum_{i=1}^p \frac{1}{(1-x)^{p+q-i+1}}\sum_{m=0}^\infty(xy)^m\binom{i+m-2}{m-1} =\sum_{i=1}^p\frac{1}{(1-x)^{p+q-i+1}}\left(\frac{xy}{(1-xy)^i}[i\neq 1]+\frac{1}{1-xy}[i=1]\right) =\frac{1}{(1-x)^{p+q+1}}\left( (1-x)+\sum_{i=1}^p\frac{(1-x)^i}{(1-xy)^i}xy\right) =\frac{1}{(1-x)^{p+q+1}}\left( (1-x)+xy \frac{1-\left( \frac{1-x}{1-xy}\right)^p}{1- \frac{1-x}{1-xy}}\frac{1-x}{1-xy}\right) =\frac{1}{(1-x)^{p+q}}\left(1+ y \frac{1-\left( \frac{1-x}{1-xy}\right)^p}{1-y}\right) =\frac{1}{(1-x)^{p+q}(1-y)}\left(1-y\frac{(1-x)^p}{(1-xy)^p} \right) =\frac{1}{(1-x)^q(1-y)}\left( \frac{1}{(1-x)^p}-\frac{y}{(1-xy)^p}\right)

证毕。

也许你会问，这仅仅是用生成函数证明了结果，能否用它发现结果呢？
在得到这个和式的生成函数的封闭形式后，总会尝试将其整理，看看能不能简单地计算吧。这样大概就能发现答案？