Как придумать комбинаторное тождество

34

Как придумать комбинаторное тожество

В различных задачках, да и в задачнике «Кванта», часто встречаются тожества, содержащие биоминальные коэффициенты $C_k^i$. Довольно часто удается их доказать методом математической индукции, иногда различными хитрыми преобразованиями, но эти доказательства, как правило, оставляют чувство неудовлетворенности: из них совершено неясно, как же было придумано данное тожество, как вообще нахождение новых тожества.

Здесь мы укажем несколько примов, позволяющих придумывать подобные тожества. В частности, мы обьясим, каким образом мы когда-то придумали задачу М470; об этом спрашивал в письме в «Квант» дагестанский школьник А. Габибов.

Представим себе, что нам нужно найти $\sum_{k=1}^{n} kx^{k-1}$. Попробуем воспользовать, где нам встречалось выражение $kx^{k-1}$. Конечно же, в формуле $(x^k)' = kx^{k-1}$. Наша договора «убивает» задачу; действительно,

$$\left( \sum_{k=1}^{n} x^k \right)' = \sum_{k=1}^{n} (x^k)' = \sum_{k=1}^{n} kx^{k-1}.$$

С другой стороны,

$$\left( \sum_{k=1}^{n} x^k \right)' = \left( \frac{x^{n+1}-x}{x-1} \right)' =$$

$$= \frac{((n+1)x^n-1)(x-1)-(x^{n+1}-x)}{(x-1)^2} =$$

$$= \frac{1}{(1-x)^2} + \frac{nx-n-1}{(1-x)^2} x^n.$$

(В этой выкладке мы, естественно, предполагали, что $x \neq 1$.) Значит,

$$\sum_{k=1}^{n} kx^{k-1} = \frac{1}{(1-x)^2} + \frac{nx-n-1}{(1-x)^2} x^n. \quad (1)$$

Тепер попытаемся найти

$$\sum_{k=1}^{n} k(k-1)x^{k-2}. \quad (\text{Особенности человекого характера побуждают повторить процедуру, которая помогла нам ранее в анализной ситуации...})$$

(Д. Пойя «Математическое открытие», М., «Наука», 1970, с. 88). Так повторим ее!

$$\sum_{k=1}^{n} k(k-1)x^{k-2} =$$

$$= \sum_{k=1}^{n} (kx^{k-1})' = \left( \sum_{k=1}^{n} kx^{k-1} \right)' =$$

$$= \left( \frac{1}{(1-x)^2} + \frac{nx-n-1}{(1-x)^2} x^n \right)' = \frac{2}{(1-x)^3} +$$

$$+ \frac{n(1-x)^2+2(1-x)(nx-n-1)}{(1-x)^4} x^n +$$

$$+ \frac{n(nx-n-1)}{(1-x)^2} x^{n-1}. \quad (2)$$

Равенства (1) и (2) весыгагромодки. На их основе можно получить (при $|x| < 1$) более красивую формулу

$$\sum_{k=0}^{\infty} C_{k+n}^n x^k = \frac{1}{(1-x)^{n+1}},$$

но ее вывод выходит за рамки школьной программы.

Расскажем теперь об одном примеем, который позволяет получить «новые» тожества из «старых». Расстояние хорошего извлечения формулу Ньютона

$$(1+x)^n = \sum_{i=0}^{n} C_i^n x^i.$$

Профиференцируем это равенство. Получаем

$$n(1+x)^{n-1} = \sum_{i=1}^{n} iC_i^n x^{i-1}. \quad (3)$$

Положив в равенстве (3) $x=1$ и $x=-1$, найдем.