Сумма всех сочетаний из $n$ по $k$: $$\sum_{k=0}^{n} \binom{n}{k} = 2^n$$

Используем бином Ньютона: $$ (a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k $$ Подставим $a = 1$, $b = 1$: $$ (1 + 1)^n = \sum_{k=0}^{n} \binom{n}{k} \cdot 1^{n-k} \cdot 1^k = \sum_{k=0}^{n} \binom{n}{k} = 2^n $$

Сумма $\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}$

Заметим, что при $k = 0$: $$ k \binom{n}{k} = 0 \cdot \binom{n}{0} = 0 $$ Поэтому сумму можно начать с $k = 1$: $$ \sum_{k=0}^{n} k \binom{n}{k} = \sum_{k=1}^{n} k \binom{n}{k} $$ Рассмотрим выражение: $$ k \binom{n}{k} = k \cdot \frac{n!}{k!(n-k)!} $$ Упростим: $$ = \frac{k \cdot n!}{k \cdot (k-1)! \cdot (n-k)!} = \frac{n!}{(k-1)! (n-k)!} $$ Теперь выделим $n$: $$ n! = n \cdot (n-1)! \quad \Rightarrow \quad \frac{n \cdot (n-1)!}{(k-1)! (n-k)!} $$ Заметим, что: $$ \frac{(n-1)!}{(k-1)! (n-k)!} = \binom{n-1}{k-1} $$ Поскольку $(n - k) = (n - 1) - (k - 1)$, то: $$ \binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)! \cdot ((n-1) - (k-1))!} = \frac{(n-1)!}{(k-1)! (n-k)!} $$ Следовательно: $$ k \binom{n}{k} = n \binom{n-1}{k-1} $$ Подставляем в сумму: $$ \sum_{k=1}^{n} k \binom{n}{k} = \sum_{k=1}^{n} n \binom{n-1}{k-1} $$ Выносим константу \( n \) за знак суммы: $$ = n \sum_{k=1}^{n} \binom{n-1}{k-1} $$ Замена переменной $j = k - 1$, тогда:

• При $k = 1$: $j = 0$
• При $k = n$: $j = n - 1$

Сумма становится: $$ n \sum_{j=0}^{n-1} \binom{n-1}{j} $$ Но это — полная сумма всех биномиальных коэффициентов для $n-1$: $$ \sum_{j=0}^{n-1} \binom{n-1}{j} = 2^{n-1} $$ Итак: $$ \sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1} $$

$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$

Способ 1

$$\sum_{k=0}^n \binom{n}{k}^2=\sum_{k=0}^n \left(\binom{n}{k}\binom{n}{k}\right)$$ Т.к. $\binom{n}{k}=\binom{n}{n-k}$, то: $$=\sum_{k=0}^n \left(\binom{n}{k}\binom{n}{n-k}\right)$$ Рассмотрим слогаемое: $$\binom{n}{k}\binom{n}{n-k}$$ Это — количество способов выбрать $k$ объектов из набора из $n$ объектов, а затем выбрать $n-k$ объектов из другого набора из $n$ объектов при фиксированном $k$. Т.о., сумма этих слогаемых по всем $k$ от $0$ до $n$ учитывает все возможные способы выбрать $n$ объектов из $2n$ объектов. Т.е. $$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$$

Способ 2

Вычислим для нескольких значений $n$:

$\binom{0}{0}^2 = 1$

$\binom{1}{0}^2 + \binom{1}{1}^2 = 1 + 1= 2$

$\binom{2}{0}^2 + \binom{2}{1}^2 + \binom{2}{2}^2 = 1 + 4 + 1 = 6$

$\binom{3}{0}^2 + \binom{3}{1}^2 + \binom{3}{2}^2 + \binom{3}{3}^2 = 1 + 9 + 9 + 1 = 20$

$\binom{4}{0}^2 + \binom{4}{1}^2 + \binom{4}{2}^2 + \binom{4}{3}^2 + \binom{4}{4}^2 = 1 + 16 + 36 + 16 + 1 = 70$

Гипотеза: $1,2,6,20,70,\dots$ - образуют последовательность центральных биномиальных коэффициентов (центральные коэффициенты четных рядов в треугольнике Паскаля). Т.е.: $$ \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} $$ Теперь докажем эту гипотезу комбинаторным способом. Сколькими способами можно выбрать $n$ объектов из $2n$ различных?
Pазобьём $2n$ объектов на две группы по $n$: группа $A$ и группа $B$. Чтобы выбрать $n$ объектов, можно взять $k$ из A и $n-k$ из $B$, где $k = 0, 1,\dots, n$. Т.е. кол-во способов при фиксированном $k$: $$ \binom{n}{k} \cdot \binom{n}{n-k} = \binom{n}{k}^2 $$ Т.о. общее кол-во способов выбрать $n$ объектов из $2n$ равно сумме по всем $k$ от $0$ до $n$: $$ \binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2 $$ Гипотеза доказана.