Квант
Математический кружок

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

Курляндчик Л. Д., Лисицкий А. Д.

Квант 1980, №5с. 34Тег KJUA

34

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

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

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

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

(∑k=1nxk)′=∑k=1n(xk)′=∑k=1nkxk−1.\left( \sum_{k=1}^{n} x^k \right)' = \sum_{k=1}^{n} (x^k)' = \sum_{k=1}^{n} kx^{k-1}.

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

(∑k=1nxk)′=(xn+1−xx−1)′=\left( \sum_{k=1}^{n} x^k \right)' = \left( \frac{x^{n+1}-x}{x-1} \right)' =

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

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

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

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

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

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

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

∑k=1nk(k−1)xk−2=\sum_{k=1}^{n} k(k-1)x^{k-2} =

=∑k=1n(kxk−1)′=(∑k=1nkxk−1)′== \sum_{k=1}^{n} (kx^{k-1})' = \left( \sum_{k=1}^{n} kx^{k-1} \right)' =

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

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

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

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

∑k=0∞Ck+nnxk=1(1−x)n+1,\sum_{k=0}^{\infty} C_{k+n}^n x^k = \frac{1}{(1-x)^{n+1}},

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

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

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

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

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

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