# Help with a Summation

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?

-

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

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

-

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

-

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

-
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 $$(1 + x)^{n-4} = \sum_{r=0}^{n-4} \dbinom{n-4}{r} x^r.$$ Derive both sides and then set $x = 1$ to get... then use the other summation.

-