замечательное свойство производящей функции чисел Каталана

[maxal]

Хорошо известно, что производящая функция для чисел Каталана $C_n = \frac{1}{n+1}\binom{2n}{n}$ имеет вид:

$$\mathcal{C}(x) = \sum_{n=0}^{\infty} C_n\cdot x^n = \frac{1-\sqrt{1-4x}}{2x}.$$

Докажите, что для всех целых $m\geq 1$ и $n\geq 0$ коэффициент при $x^n$ в $\mathcal{C}(x)^m$ равен $\frac{m}{n+m}\binom{2n+m-1}{n}$. То есть,

$$\left(\sum_{n=0}^{\infty} \frac{1}{n+1}\binom{2n}{n} \cdot x^n\right)^m = \sum_{n=0}^{\infty} \frac{m}{n+m}\binom{2n+m-1}{n} \cdot x^n.$$

[RabbitXO]

Возведем в квадрат равенство $C(x)=\frac{1-\sqrt{1-4x}}{2x}$. Получим, что $C(x)^2=\frac{1-\sqrt{1-4x}-2x}{2x^2}$ или $C(x)^2=\left(C(x)-1\right)/x$. Очевидно, что

$$ C(x)^m=\left(C(x)^{m-1}-C(x)^{m-2}\right)/x,\ m\geqslant 2.\ \ (1) $$

Обозначим $c_n^m$ - коэффициент при $x^n$ в $C(x)^m$. Требуется доказать, что

$$ c_n^m=\frac{m}{n+m}\binom{2n+m-1}{n}, m\geqslant1,\ n\geqslant 0. \ \ (2) $$

При $m=1$ последнее равенство вытекает из определения. Покажем, что оно справедливо для $m=2$.
Из (1) следует $C(x)^2=\left(\sum\limits_{n=0}^\infty C_n x^n-1\right)/x=\sum\limits_{n=1}^\infty C_n x^{n-1}$, т.к. $C_0=1$. Таким образом $c_n^2=C_{n+1}=\frac{1}{n+2}\binom{2(n+1)}{n+1}=\frac{2}{n+2}\binom{2n+1}{n}$. Значит (2) справедливо и при $m=2$.

Предположим, что (2) справедлив для $1\leqslant m\leqslant k-1$. Покажем, что (2) выполняется для $m=k$. Воспользуемся (1), предположением и равенством $c_0^m=1,\ m\geqslant 1$.

$$ C(x)^k=\left(\sum\limits_{n=0}^\infty c_n^{k-1}x^n-\sum\limits_{n=0}^\infty c_n^{k-2}x^n\right)/x=\sum\limits_{n=0}^\infty(c_{n+1}^{k-1}-c_{n+1}^{k-2})x^n. $$

Таким образом

$$c_n^k=c_{n+1}^{k-1}-c_{n+1}^{k-2}=\frac{k-1}{n+k}\binom{2(n+1)+k-2}{n+1}-\frac{k-2}{n+k-1}\binom{2(n+1)+k-3}{n+1}.$$

После не хитрых преобразований получим, что $c_n^k=\frac{k}{n+k}\binom{2n+k-1}{n}$. И значит равенство (2) справедливо при всех $m\geqslant1$.