Rambler's Top100





13
(по индуктивному предположению),
1
1
1 n
ln
n
ln
n
ln
CCC
по свойству
4). Пятое свойство доказано.
Теорема 4 (бином Ньютона).
n
k
kk
n
nn
nnn
n
xCxCxCxCx
0
221
....1)1(
.
Доказательство. Второе равенство представляет собой не что
иное, как разные записи одной и той же суммы. Слева стоит эта сумма в
“развернутом” виде, а справа эта же сумма, записанная с помощью зна-
ка суммирования. Поэтому доказываем первое равенство.
Рассмотрим выражение:
)1).....(1)(1(
21 n
xxxA
.
Раскрыв скобки, получим сумму
n
i nji nii
niiijii
k
k
xxxxxxxxxA
1 1 ...1
21
1
21
.........,...1
.
В первой сумме количество слагаемых равно количеству элементов
множества
},,...,2,1{ nS
то есть
1
n
Cn
. Во второй сумме количе-
ство слагаемых равно количеству двухэлементных подмножеств n-
элементного множества S, то есть равно
2
n
C
. Число слагаемых в k-ой
сумме равно количеству k-элементных подмножеств n-элементного
множества S , то есть равно
k
n
C
. Поэтому, если положить в A
xxxx
n
...
21
, то получим
nkk
nnn
n
xxCxCxCx ......1)1(
221
. Теорема доказана.
Следствие 5.
n
n
k
nn
n
CCC ......12
1
.
Доказательство. Положим в формуле бинома
1x
, получим до-
казываемое равенство.
Равенство из следствия 5 имеет очень важный комбинаторный
смысл. В правой части:
0
1
n
C
- количество пустых подмножеств n-
элементного множества S,
1
n
Cn
количество 1-элементных подмно-
жеств n-элементного множества,
k
n
C
- число k элементных подмно-
жеств n-элементного множества и так далее. Сумма в правой части
представляет собой количество всех подмножеств n–элементного мно-
жества, а записанное равенство показывает, что таких подмножеств бу-
дет 2
n
. Таким образом, следствие можно сформулировать так: если n(S)