2
$\begingroup$

I need to prove that $\sum_{k=0}^n k \binom{n}k=n\cdot2^{n-1}$ using Combinatorial argument

I know this can be done by differentiating binomial expansion of $(1+x)^n$ and then putting $x=1$ , but how shall I do it combinatorially?

$\endgroup$
7
$\begingroup$

How many ways are there to colour one of $n$ balls red and paint the rest either blue or green?

First pick the red ball. Then select a subset of the remaining $n-1$ balls to paint them blue. Paint the rest green. This gives $$n\cdot 2^{n-1}.$$

Or: Pick the number $k$ of non-green balls. Pick one of these $k$ balls as red. paint the remaining $k-1$ of these balls blue. And of course the balls not picked in the first step are painted green. This gives for each $k$ a count of $k{n\choose k}$ ways, so in total $$\sum_{k=0}k{n\choose k}.$$

$\endgroup$
0
$\begingroup$

The left-hand side counts the number of pointed $k$-subsets of $X$ for $k=0,\cdots,n$ and the right-hand side counts the number of pointed subsets of $X$ full stop, where $|X|=n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.