6
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your help, I appreciate it. $\endgroup$ – Mike Smith Apr 19 '13 at 13:24
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you as well, this is helpful. $\endgroup$ – Mike Smith Apr 19 '13 at 13:26

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.