Числа Каталана

[Zealint]

Существует множество способов получить формулу для чисел Каталана:

$$ C_n = \frac{1}{n+1}\left(2n \atop n\right). $$

Некоторые из них мне известны. Но здесь я хочу задать такой вопрос. Предположим, что мы не знаем, что есть такие замечательные числа, но вывели одно рекуррентное соотношения (которому они удовлетворяют):

$$ C_n = \sum_{k=0}^{n-1} C_kC_{n-k-1}, \quad n>0 \mbox{ и } C_0=1. $$

Далее, используя технику производящих функций мы получаем такое выражение:

$$ G(z) = \frac{1-\sqrt{1-4z}}{2z} = \sum_{n=0}^{\infty} \frac{z^n}{n+1}\left(2n \atop n\right). $$

[ не важно, как это раскладывается в ряд, здесь все правильно ]. Теперь вопрос такой: как доказать, что формула, полученная таким способом верна? Ведь манипуляции с производящими функциями в моём выводе не доказаны строго, поэтому выведенную формулу надо проверить. Для этого нужно подставить её в исходное рекуррентное соотношение. Но после подстановки получается такая жуткая вещь:

$$ \frac{1}{n+1}\left(2n \atop n\right) = \sum_{k=0}^{n-1}\frac{1}{k+1}\left(2k \atop k\right) \frac{1}{n-k}\left(2n -2k-2 \atop n-k-1\right), $$

упростить которую получается только через гипергеометрические преобразования и свойства гамма-функций. А мне нужно как-то проще. Без наворотов. Может кто знает? То есть мне нужно проверить числа Каталана именно через это рекуррентное соотношение, сложное доказательство (и очень длинное) я в принципе придумал, но мне нужно очень простое и короткое. Если оно есть.

Ещё известно вот такое соотношение (которое получается из уже известной формулы):

$$C_{n+1}=C_{n}\frac{4n+2}{n+2},$$

Но с его помощью тоже мало что получается.

[Хорхе]

Не знаю ничего простого и короткого "именно через рекуррентное соотношение". А чем не нравятся производящие функции? Там все строго и шоколадно, особенно если воспользоваться методом рака.

[Zealint]

Хорхе в сообщении #312029 писал(а):

Не знаю ничего простого и короткого "именно через рекуррентное соотношение". А чем не нравятся производящие функции? Там все строго и шоколадно, особенно если воспользоваться методом рака.

Производящая функция получилась из рекуррентного соотношения. Доказательства того, что разложение производящей функции в ряд даёт именно то, что нужно у меня нет. Поэтому после разложения её в ряд нужно проверить формулу непосредственной подстановкой.

[Хорхе]

Так вот я и предлагаю методом рака -- задом наперед.

Взять функцию, что у Вас получилась, написать уравнение, которому она удовлетворяет, вывести отсюда, что коэффициенты разложения удовлетворяют нужному рекуррентному соотношению (теорема про коэффициенты произведения степенных рядов) и возрадоваться, ибо последовательность с такими свойствами единственна.