Maths Olympiad Prep

Track / Stage 4 / 124 of 340 #384 of 1964

Problem 384

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

Calculate the sum

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

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

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 reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.