# How can I solve $\sum\limits_{i = 1}^k i \binom{k}{i-1}$

If anyone could help with the steps in solving this summation. I've been playing with it most of the day. It started from me trying to prove $\sum\limits_{i=0}^{k+1} \left(i\binom{k+1}{i}\right) = (k+1)2^k$. I used Pascal's rule to simplify this a little bit, but I think I've just been looking at it too long, and thought I'd see if anyone had any good initial hints. Thanks in advance for any help.

Algebraic proof:

Consider $$(1+x)^{k+1} = \sum_{i=0}^{k+1} \dbinom{k+1}i x^i \tag{\star}$$ Differentiate both sides of $(\star)$ with respect to $x$ to get $$(k+1) (1+x)^k = \sum_{i=0}^{k+1}i \cdot \dbinom{k+1}i x^{i-1} \tag{\perp}$$ Now set $x=1$ in $(\perp)$ to get $$(k+1)2^k = \sum_{i=0}^{k+1}i \cdot \dbinom{k+1}i$$

Combinatorial proof:

We want to form a team for a local football game. Our local community has $k+1$ people. The team can consist of any number of people but must have one captain.

There are two ways to do this.

The first way is to choose a captain, this can be done in $k+1$ ways and then we have $k$ people from which we can form $2^k$ different combinations to form a team along with the captain. This gives us the total number of teams with a captain that can be formed as $$\color{red}{(k+1) 2^k} \tag{\spadesuit}$$

The second way is to form a team of $i$ people, which can be done in $\dbinom{k+1}i$ ways and from these $i$ people choose a captain, which can be done in $i$ ways. Now $i$ can vary from $0$ to $k+1$ and this gives us $$\color{blue}{\sum_{i=0}^{k+1}i \cdot \dbinom{k+1}i} \tag{\clubsuit}$$

Since $(\spadesuit)$ and $(\clubsuit)$ count the same thing, they have to be equal.

Once you prove this the summation $$\sum_{i=1}^k i \cdot \dbinom{k}{i-1}$$ is trivial. Let $i-1 = j$, We then get that $$\sum_{i=1}^k i \cdot \dbinom{k}{i-1} = \sum_{j=0}^{k-1}(j+1) \cdot \dbinom{k}j = -(k+1) \dbinom{k}k + \sum_{j=0}^{k}(j+1) \cdot \dbinom{k}j$$ This gives us $$-(k+1) + k 2^{k-1} + 2^k$$

• Thank you for your help, I appreciate it. – Mike Smith Apr 19 '13 at 13:24

The following is a mean proof.

If we toss a fair coin $n$ times, the mean number of heads, by symmetry, is $\dfrac{n}{2}$.

But the mean is also $$\sum_{i=0}^n i\binom{n}{i}\frac{1}{2^n}.$$

Remark: Minor manipulation deals with the variants mentioned in the OP. For example, changing $i\binom{n}{i}$ to $(i+1)\binom{n}{i}$ adds $2^n$ to the sum.

• Thank you as well, this is helpful. – Mike Smith Apr 19 '13 at 13:26