Задача
COM-B2-M01-P005 Отмеченный элемент
#5
★★☆☆☆ Уровень 2 из 5
Докажите \(\sum_{k=0}^n k\binom nk=n2^{n-1}\).
Считайте пары \((A,x)\), где \(x\in A\).
Если сначала выбрать \(A\) размера \(k\), то отмеченный элемент \(x\in A\) выбирается \(k\) способами, получаем левую часть. Если сначала выбрать \(x\), есть \(n\) вариантов, а остальные элементы подмножества выбираются произвольно: \(2^{n-1}\) вариантов. Получаем \(n2^{n-1}\).
Первое важное тождество через пары.