2014-06-08
Дана последовательность $a_{0} = 1, a_{n+1} = \sum_{i=0}^{n}a_{i}a_{n-i} (n \geq 0)$. Выразить в явном виде $a_{n}$ через $n$.
Решение:
Покажем, что
$a_{n} = \frac{C_{2n}^{n}}{n+1}$
Для этого рассмотрим функцию
$F(x) = \frac{1}{2x} (1 - \sqrt{1-4x}), 0 < |x| < \frac{1}{4}$
Так как функция $(1+y)^{\alpha}$ раскладывается в степенной
$(1+y)^{\alpha} = \sum_{n=0}^{\infty} \frac{\alpha (\alpha - 1) \cdots (\alpha – n + 1)}{n!} y^{n}, |y| < 1$,
то
$\sqrt{1 – 4x} = \sum_{n=0}^{\infty} \frac{\left ( \frac{1}{2} \right ) \cdot \left ( - \frac{1}{2} \right ) \cdot \cdots \cdot \left ( \frac{3}{2} - n \right )}{n!} (4x)^{n} = 1 - \sum_{n=1}^{\infty} 2^{n} \frac{1 \cdot 3 \cdot \cdots \cdot (2n-3)}{n!} x^{n} = 1 - \sum_{n=1}^{\infty} 2 \frac{(2n-2)!}{n!(n-1)!} x^{n}, |x| < \frac{1}{4}$,
откуда
$F(x) = \sum_{n=1}^{\infty} \frac{(2n-2)!}{n!(n-1)!} x^{n-1} = \sum_{n=0}^{\infty} \frac{(2n)!}{(n!)^{2}(n+1)} x^{n} = \sum_{n=0}^{\infty} \frac{C_{2n}^{n}}{n+1}, 0 < |x| < \frac{1}{4}$.
(Мы считаем $0! = 1$, а произведение, сомножители отсутствуют, равным 1.)
Функция $F(x)$ удовлетворяет тождеству
$1 + x (F(x))^{2} \equiv F(x)$.
Раскладывая левую и правую части в степенные приравнивая коэффициенты при, мы получаем
$\sum_{i=0}^{n} \frac{C_{2i}^{i}}{i+1} \frac{C_{2(n-i)}^{n-i}}{n – i +1} = \frac{C_{2(n+1)}^{n+1}}{n+2}$.
Отсюда легко вывести по индукции, что $a_{n} = \frac{C_{2n}^{n}}{n+1}$.