2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 замечательное свойство производящей функции чисел Каталана
Сообщение18.11.2015, 20:14 
Аватара пользователя
Хорошо известно, что производящая функция для чисел Каталана $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.$$

 
 
 
 Re: замечательное свойство производящей функции чисел Каталана
Сообщение26.11.2015, 16:58 
Возведем в квадрат равенство $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$.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group