Question

Докажите тождества Cn^1+2Cn^2+…+nCn^n=2^n-1

Answer 1

Тождество неверное. Скорее уж будет так

$C^1_n+2C_n^2+...+nC^n_n=n\cdot 2^{n-1}$

$C^1_n+2C^2_n+...+nC^n_n=\sum^{n}_{k=1}k\cdot C^k_n$

Пользуясь свойством $\sum^{n}_{k=0}k\cdot C^k_n=n\cdot 2^{n-1}$, мы имеем

$\sum^n_{k=1}k\cdot C^k_n=n\cdot 2^{n-1}$

Можно доказать без всяких свойств чисел сочетаний. По формуле бинома Ньютона $n\cdot 2^{n-1}=n\cdot (1+1)^{n-1}=n\cdot \sum^{n-1}_{p=0}C^p_{n-1}$. В свою очередь при любом p выполняется равенство:

$n\cdot C^p_{n-1}=\frac{n(n-1)}{p!(n-1-p)!}\cdot \frac{p+1}{p+1}=\frac{n!(p+1)}{(p+1)![n-(p+1)]!}=(p+1)C^{p+1}_n$

Следовательно, $n\cdot 2^{n-1}=\sum^{n-1}_{p=0}(p+1)C^{n+1}_n$. Преобразим индекс суммирования, положив $p+1=k$. Имеем:

$\sum^{n-1}_{p=0}(p+1)C^{p+1}_n=\sum^{n}_{k=1}kC^k_n$

Answer 2

Для доказательства данного тождества, мы можем воспользоваться биномиальной теоремой и индукцией.

Биномиальная теорема утверждает, что для любых чисел $a$ и $b$ и натурального числа $n$, верно следующее разложение:

$(a + b)^n = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-2}b^2 + \ldots + \binom{n}{n-1}ab^{n-1} + \binom{n}{n}b^n$.

В данном случае, мы можем взять $a = 1$ и $b = 1$, и тогда биномиальное разложение примет вид:

$(1 + 1)^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n-1} + \binom{n}{n}$.

Известно, что $(1 + 1)^n = 2^n$.

Теперь давайте рассмотрим сумму $\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n-1} + \binom{n}{n}$. Эта сумма представляет собой количество всех подмножеств набора из $n$ элементов, что также равно $2^n$.

Таким образом, $\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n-1} + \binom{n}{n} = 2^n$.

А ваше исходное утверждение выглядит как:

$C_n^1 + 2C_n^2 + \ldots + nC_n^n = 2^n - 1$.

Обратите внимание, что $\binom{n}{k} = kC_n^k$, поэтому можно записать:

$C_n^1 + 2C_n^2 + \ldots + nC_n^n = \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n}$.

Мы уже выяснили, что это равно $2^n$, но по вашему утверждению оно должно быть равно $2^n - 1$.

Таким образом, данное утверждение $C_n^1 + 2C_n^2 + \ldots + nC_n^n = 2^n - 1$ неверно.