6
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – user940 Jun 20 '13 at 16:31
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – user83200 Jun 20 '13 at 8:24
  • $\begingroup$ @user83200, that's what Telescoping means. Also, just putting values of $k$ from $0,1,\cdots,p-1,p$ will show that $\endgroup$ – lab bhattacharjee Jun 20 '13 at 8:29
  • $\begingroup$ I did not spot your recent addition until now ... the 1/(p+1) factor should be (p+1), right? $\endgroup$ – user83200 Jun 20 '13 at 8:29
  • $\begingroup$ @user83200, thanks for your observation. Sorry for the mistake. Rectified. $\endgroup$ – lab bhattacharjee Jun 20 '13 at 8:38
2
$\begingroup$

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

$\endgroup$

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.