Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been trying to figure out why the summation of $(r+2)\binom{n-4}{r}$ from $r=0$ to $(n-4)$ is equal to $n2^{n-5}$, but I can't seem to get it to work. The only thing I can think of that would be relevant is that the summation of $\binom{n}{k}$ from $k=0$ to $n$ is $2^n$, but I can't get it to follow. Could anyone help me with this, either with a solution or by telling me what method I'm meant to use? Are there by any chance any facts I'm meant to know?

share|improve this question

5 Answers 5

You can decompose your sum as $$\sum_{r=0}^{n-4} r {n-4 \choose r}+\sum_{r=0}^{n-4} 2{n-4 \choose r}$$
The second sum is $2\cdot 2^{n-4}=2^{n-3}$ by the formula you gave.
You also require the result that $$\sum_{r=0}^{n}r{n \choose r}=n2^{n-1}$$ Which gives the first sum as $(n-4)\cdot 2^{n-5}$ Your full sum is therefore $2^{n-5}(n-4+4)=n2^{n-5}$

I don't know if you have proved these identities yourself, but if not, consider the binomial expansions of $(1+x)^n$ and its derivative at $x=1$.

share|improve this answer
    
Thank you very much for your help! I did prove the first one just by considering the number of subsets of {1,...,n} and applying double counting. I'm now going to try and prove the second one. This would be a key piece I'm missing. :D –  user60126 Jan 29 '13 at 18:28
    
You're welcome! I don't know of a counting argument for the other identity; I only know the binomial theorem proof. –  Daniel Littlewood Jan 30 '13 at 19:30

Hint: Use the binomial identity

$$r \binom{n-4}{r} = (n-4) \binom{n-5}{r-1}$$

Keep in mind that $\binom{n-5}{-1} = \binom{n-5}{n-4} = 0.$

share|improve this answer

$$\sum_{r=o}^{n-4}(r+2)\binom{n-4}{r}=\sum_{r=0}^{n-4}r\binom{n-4}{r}+2\sum_{r=0}^{n-4}\binom{n-4}{r}=$$ $$=\sum_{r=0}^{n-4}(n-4)\binom{n-5}{r-1}+2\cdot2^{n-4}=(n-4)\sum_{j=0}^{n-5}\binom{n-5}{j}+2^{n-3}=$$ $$=(n-4)2^{n-5}+2^{n-3}=n\cdot 2^{n-5}-4\cdot2^{n-5}+2^{n-3}=$$ $$=n\cdot 2^{n-5}-2^2\cdot2^{n-5}+2^{n-3}=n\cdot 2^{n-5}-2^{n-3}+2^{n-3}=n\cdot 2^{n-5}$$ Using $$k\binom{n}{k}=n\binom{n-1}{k-1}\Rightarrow r\binom{n-4}{r}=(n-4)\binom{n-5}{r-1}$$

share|improve this answer

First of all,

$$\sum_{r=0}^{n-4}{n-4 \choose r}(r+2)$$

is the same as (where $m = n-4$)

$$\sum_{r=0}^{m}{m \choose r}(r+2) = \sum_{r=0}^{m}{m \choose r}r + 2\sum_{r=0}^{m}{m \choose r}$$

As you've said, using the binomial theorem,

$$2\sum_{r=0}^{m}{m \choose r}1^r 1^{m-r} = 2(1+1)^m = 2^{m+1}$$

The second part, can be explained as having a bunch of people ($m$), in how many ways can you pick a group and designate one of them as a leader:

  1. You either pick a group of size $r$ (${m \choose r}$ ways) and pick one as the leader ($r$ ways), for every group size - Leading to sum:

$$\sum_{r=0}^{m}{m \choose r}r$$

  1. Pick one as the leader ($m$ choices) and for every one of the remainning people ($m-1$) decide whether they are in the group or not ($2^{m-1}$ ways) leading to

$$m 2^{m-1}$$

So that together you have

$$m 2^{m-1} + 2^{m+1} = (m+4) 2^{m-1} = n 2 ^{-5}$$

share|improve this answer
    
Thank you very much for the reasoning to the second part. That makes perfect sense. I didn't think to change n-4 to m! –  user60126 Jan 29 '13 at 18:33

The summation you quote will be useful.

Then note the following trick, which has a vast scope (http://www.math.upenn.edu/~wilf/DownldGF.html).

Start with \begin{equation} (1 + x)^{n-4} = \sum_{r=0}^{n-4} \dbinom{n-4}{r} x^r. \end{equation} Derive both sides and then set $x = 1$ to get... then use the other summation.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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