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$