# Partial sums of binomial coefficients: $\sum\limits_{k=0}^p\binom{n}{k} (n-2 k) = (p+1)\binom n{p+1}$

I assume this is simple. However, my math is rusty and my frustration rising. How can one show that

$$\sum _{k=0}^p \binom{n}{k} (n-2 k) = (p+1) \binom{n}{p+1}$$

holds?

• This is formula (5.18) on page 166 of Concrete Mathematics by Graham, Knuth, and Patashnik. The suggested proof there is by induction on $p$. – user940 Jun 20 '13 at 16:31

$$\binom nk (n-2k)=\frac{n!}{(n-k)! k!} (n-k-k)$$

$$=n\left(\frac{(n-1)!}{(n-1-k)!k!}-\frac{(n-1)!}{\{(n-1)-(k-1)\}!(k-1)!}\right)$$

$$=n\left(\binom{n-1}k -\binom{n-1}{k-1}\right)$$

Observing the Telescoping Sum/Series,

$$\sum _{k=0}^p \binom{n}{k} (n-2 k) = n\cdot \binom{n-1}p$$

$$=n\cdot\frac{(n-1)!}{(n-1-p)!p!}=(p+1)\cdot \frac{n!}{\{n-(p+1)\}!(p+1)!}=(p+1)\cdot\binom n{p+1}$$

• Heureka! If you had remarked that subsequent terms cancel when performing the sum, it would have been easier (my background is non-mathematical) ... Thank you for your help! – user83200 Jun 20 '13 at 8:24
• @user83200, that's what Telescoping means. Also, just putting values of $k$ from $0,1,\cdots,p-1,p$ will show that – lab bhattacharjee Jun 20 '13 at 8:29
• I did not spot your recent addition until now ... the 1/(p+1) factor should be (p+1), right? – user83200 Jun 20 '13 at 8:29
• @user83200, thanks for your observation. Sorry for the mistake. Rectified. – lab bhattacharjee Jun 20 '13 at 8:38

The answer by lab bhattacharjee made me wonder if there is a simple bijective explanation for this curious identity (curious to me because I had never seen it before, and because I think that $(a+bk)\binom nk$ with $a,b,n$ constant is only summable on$~k$ in closed form for $(a,b)=(n,-2)$). Indeed, in spite of the forbidding looking factorials, the only identities really needed are the "absorption" identity $k\binom nk=n\binom{n-1}{k-1}$ and its variant $(n-k)\binom nk=n\binom{n-1}k$). Here is how:\begin{aligned} \sum_{k=0}^p (n-2k)\binom nk &= \sum_{k=0}^p \left((n-k)\binom nk -k\binom nk\right) \\&= \sum_{k=0}^p \left(n\binom{n-1}k-n\binom{n-1}{k-1}\right) \\&=n\left(\binom{n-1}p-\binom{n-1}{-1}\right) \\&=n\binom{n-1}p \\&= (p+1)\binom n{p+1}. \end{aligned} Now on one hand the absorption laws have a simple bijective proof, and on the other hand, being polynomial identities in$~n$ (of degrees $k,k+1$, respectively) they are valid without the assumption that $n$ is a positive integer. Thus the identity proved holds for arbitrary $n$ (negative, fractional, complex, indeterminate) and for any non-negative integer$~p$ (no need to assume $p\leq n$).

Now for a bijective proof, consider a set of $n$ different fruits, of which we select one, and of which a subset of at most $p$ turns out to be bad bad; we count the number of possible configurations, but with a minus sign in case the selected fruit is bad. Fixing a subset of $k\leq p$ bad fruits, there are $n-k$ good and $k$ bad selections possible, so this subset contributes $(n-k)-k=n-2k$ to the final sum; this sum is then given by the left hand side. Counting differently, we can cancel most configurations against one with the opposite sign by changing the good/bad status of the selected fruit (this clearly pairs up configurations); however when a there are exactly $p$ bad fruits and a good one is selected, this change cannot be done due to the "at most $p$ bad friuts" restriction. So the total configuration sum is the (nonnegative) number of those unpaired configurations, with $p$ bad fruits and a good fruit selected. These can be counted either as $n\binom{n-1}p$ (select a fruit and make $p$ of the remaining fruits bad), or as $(p+1)\binom n{p+1}$ (choose the $p+1$-subset of bad-or-selected fruits first, then choose the selected fruit among them, making it good and the others bad).