Related Theorem of Binomial Theorem

Question

Proving that for any whole number $n$, the following identity holds: $$\sum^{n}_{i=1}{n\choose{i}}i=n\times2^{n-1}$$ So, I memorized this formula for preparing for math contests, but I think it's totally useless, and less efficient than actually understand what this identity means, rather than just brute force memorizing it. I'm guessing that $n\times2^{n-1}$ can potentially mean that there're $n-1$ on-off switches, and the extra $n$ confuses me. The sum on the left doesn't really even make sense to me. Someone mind to explain this in detail to me? Thanks!

Answer 1

Method $1$: From the binomial theorem, we have $$\sum_{k=0}^n \dbinom{n}k x^k = (1+x)^n$$ Differentiate both sides to get $$\sum_{k=0}^n k \dbinom{n}k x^{k-1} = n(1+x)^{n-1}$$ Set $x=1$, to get what you want. You could obtain related results by differentiating or integrating it multiple times.

Method $2$: Another way to look at it is to realize that $$i\dbinom{n}i = n \binom{n-1}{i-1}$$ Hence, $$\sum_{k=1}^n k \dbinom{n}k x^{k-1} = n \sum_{k=1}^n \dbinom{n-1}{k-1} x^{k-1} = n \sum_{k=0}^{n-1} \dbinom{n-1}{k} x^{k} = n (1+x)^{n-1}$$

Method $3$: Combinatorial interpretation, which Danny Cheuk has already provided.

Answer 2

Hint: Imagine you're choosing a committee of $i$ people from a total of $n$ people, but then one of those $i$ people gets to be the leader.

Answer 3

One way to prove it algebraically is to notice that

$$\binom{n}i=\frac{n!}{i!(n-i)!}\cdot i=\frac{n!}{(i-1)!(n-k)!}=n\binom{n-1}{i-1}\;,\tag{1}$$

so that $$\sum_{i=1}^n\binom{n}ii=n\sum_{i=1}^n\binom{n-1}{i-1}=n\sum_{i=0}^{n-1}\binom{n-1}i=n2^{n-1}\;.$$ The identity $(1)$ is surprisingly useful.

A combinatorial proof is also possible. Start with the easy side: $n2^{n-1}$ is the way to choose one of $n$ people to be a team captain and then to choose any subset of the other $n-1$ people to fill out the team. $\binom{n}ii$ is the number of ways to pick a team of $i$ people from the original set of $n$ and then choose one of them to be the captain. Since a captain is required, the possible team sizes run from $1$ through $n$.