# Question Posted in class

Federico posted a question today about what  $\sum_{k=0}^n k\binom{n}{k}$ equals. This is what I tried out, so let me know what you think.

He showed in class how $\sum_{k=0}^n \binom{n}{k}x^k=(1+x)^n$. By differentiating both sides we get $\sum_{k=0}^n k\binom{n}{k}x^{k-1}=\sum_{k=1}^n k\binom{n}{k}x^{k-1}=n(1+x)^{n-1}$. Thus we plug 1 and get that $\sum_{k=1}^n k\binom{n}{k}=n2^{n-1}$.

Thus we have that $\sum_{k=0}^n k\binom{n}{k}=n2^{n-1}$

I tried to make sense of this combinatorially and think that it tells us that for a set $S$ such that $|S|=n$  the number of ways to choose an element of $S$ and creating a subset containing it is equal to the number of ways to choose a subset of $S$ and picking out an element from it.

For example take $\{1,2,3\}$. For the first case say we pick the element 2, then we can create the subsets $\{2\},\{1,2\},\{2,3\},\{1,2,3\}$. Since we can pick 3 elements and do this for each one, we have a total of $12=3(4)=3(2^{3-1})$. Now for the second question we can choose the empty set but have no way of choosing an element ( 0 ways), choose a 1-set and then an element($\binom{3}{1}(1)$ ways), a 2-subset and then an element($\binom{3}{2}(2)$ ways), or a 3-subset and then an elements($\binom{3}{3}(3)$ ways). Thus giving us a total of $\binom{3}{0}(0)+\binom{3}{1}(1)+\binom{3}{2}(2)+\binom{3}{3}(3)=$0+3+6+3=12  ways.

Cool way to use analysis and algebra to get a not so obvious(at least to me) combinatorial result.

1. paco9208

For an algebraic proof we can use the identity $k*\{n\choose k} = n*\{(n-1)\choose(k-1)}$ and then just factor the n out, in case the interval of convergence for such series does not include x=1.

2. Nice Paco. Dude the latex is a bit different here. To type a formula in WordPress type  without the signs .

3. ***To type a formula in WordPress type $latex Your LaTex code$ without the space between \$ and latex.

4. Three nice proofs! (Notice that there is no issue of convergence here because this is an equality of polynomials, so plugging in $x=1$ is fine.)

5. suitored

I know is kind of late for this but I just saw the video of lecture 2. Another nice interpretation is that $sum_{k=0}^{n}k {n\choose k}$ is the “weight” of $2^[n]$ if we assume that the weight of a single element is $1$. Then, if you take any element, the number of subsets containing it is $2^{n-1}$ so each element in ${1, \dots ,n}$ appears $2^{n-1}$ times in $2^[n]$. Now just multiply by because there are $n$ elements.

6. suitored

Sorry, is $2^{[n]}$ in both strange things.