Комбинаторика.Докажите тождество

Алгебраическое доказательство

Воспользуемся тем, что

2^{n+1} = C_{n+1}^0 + C_{n+1}^1 + ... + C_{n+1}^{n+1},

что верно по формуле Бинома Ньютона, где вместо a и b в (a+b)^n мы ставим 1. Сократим C_{n+1}^{0} и -1 в условии (Позже будет понятно почему берем именно C_{n+1}^{0} , а не C_{n+1}^{n+1}.) Теперь надо доказать

\sum_{i=0}^n \frac{1}{i+1}C_n^i = \sum_{i=1}^{n+1} \frac{1}{n+1} C_{n+1}^{i}

Заметим, что обе стороны — это суммы каких-то n+1 слагаемых, поэтому было бы логично доказать, что каждое слагаемое одной суммы равно слагаемому другой.
Можно попробовать доказать \frac{1}{i+1}C_n^i = \frac{1}{n+1} C_{n+1}^{i}, что окажется неверным. В таких случаях рассматриваем такой вариант:

\frac{1}{i+1}C_n^i = \frac{1}{n+1} C_{n+1}^{n-i}

Несложно показать, что обе стороны равны \frac{n!}{(i+1)!(n-i)!}

7 симпатий

У этого факта есть кстати интересное комбинаторное доказательство.

Допустим мы хотим посчитать количество способов выбрать i кружек из n. С одной стороны это C_n^i. С другой стороны мы можем добавить к этим кружкам один стакан (получится n+1 объектов), потом выбрать среди них какие-то i+1 объектов (это C_{n+1}^{i+1} способов), и выбросить среди этих выбранных один объект (это C_{n+1}^{i+1} \cdot (i+1) способов). Таким образом мы выберем из n кружек и одного стакана i объектов. Но среди выбранных может случайно оказаться стакан, что не желательно. Поэтому результат надо разделить на n+1 (подумай почему).

Тогда выходит, что C_{n+1}^{i+1} \cdot \frac{i+1}{n+1} = C_n^i. А это равносильно тому что написала @Dilnaz

5 симпатий
© 2021 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)