суммы - Конечная сумма с биномиальными коэффициентами

Аналитическое доказательство: рассмотрим функцию $%f(x)=(x+1)^n=x^n+C_n^{n-1}x^{n-1}+\cdots+C_n^kx^k+\cdots+C_n^1x+1$%. Продифференцируем: $%f'(x)=n(x+1)^{n-1}=nx^{n-1}+\cdots+kC_n^kx^{k-1}+\cdots+C_n^1$%. Подставим $%x=1$%, и получится $%f'(1)=n2^{n-1}=\sum_{k=1}^nkC_n^k$%.

Комбинаторное доказательство: рассмотрим все пары вида $%(A,a)$%, где $%a\in A\subseteq\{1,2\ldots,n\}$%, то есть все (непустые) подмножества с отмеченным элементом. Для каждого $%i$% от $%1$% до $%n$% мы выбираем $%2^{n-1}$% способами подмножество $%B\subseteq\{1,2\ldots,n\}\setminus\{i\}$%, полагая $%A=B\cup\{i\}$% и рассматривая пару $%(A,i)$%. Это значит, что пар имеется ровно $%n2^{n-1}$%. С другой стороны, считая отдельно количество $%k$%-элементных подмножеств для каждого $%k$% от $%1$% до $%n$%, мы имеем $%C_n^k$% способов выбора такого подмножества и $%k$% способов выделить в нём элемент, что даёт сумму по всем таким $%k$% чисел $%kC_n^k$%.