Olympiad Maths Prep

Track / Stage 4 / 120 of 340 #380 of 2000

Problem 380

AMC 12 late, AIME early
Combinatorics Difficulty 4.8 Find the answer

## Task 12/68

Calculate the sum

∑k=1nk⋅(nk) \sum_{k=1}^{n} k \cdot\binom{n}{k}

Official solution

It is

k⋅(nk)=kn!k!(n−k)!=n(n−1)!(k−1)![(n−1)−(k−1)]!=n⋅(n−1k−1) k \cdot\binom{n}{k}=k \frac{n!}{k!(n-k)!}=n \frac{(n-1)!}{(k-1)![(n-1)-(k-1)]!}=n \cdot\binom{n-1}{k-1}

From this, it follows that

∑k=1nk(nk)=n⋅∑k=1n(n−1k−1)=n⋅∑l=0n(n−ll)⋅1l⋅1n−1−l=n(1+1)n−1=n⋅2n−1 \sum_{k=1}^{n} k\binom{n}{k}=n \cdot \sum_{k=1}^{n}\binom{n-1}{k-1}=n \cdot \sum_{l=0}^{n}\binom{n-l}{l} \cdot 1^{l} \cdot 1^{n-1-l}=n(1+1)^{n-1}=n \cdot 2^{n-1}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.