2
$\begingroup$

How to find $$\sum_{k=0}^{n}\left |2k-n \right |\times \binom{n}{k}?$$

Wolfram Alpha cannot evaluate it. I am approaching it by breaking summation into two intervals, i.e. $\left(0, \left\lfloor\dfrac{n}{2}\right\rfloor\right)$ and $\left(\left\lceil\dfrac{n}{2}\right\rceil, n\right)$. Then evaluating $\sum k \times \dbinom{n}{k}$ and $\sum n \times \dbinom{n}{k}$ for respective intervals. From here I cannot proceed since I am unable to find these partial sums.

Any hint or different procedure will be appreciated.

$\endgroup$
  • 2
    $\begingroup$ Cross-posted: mathoverflow.net/questions/302262/… $\endgroup$ – Watson Jun 7 '18 at 12:36
  • $\begingroup$ @Jean-ClaudeArbaut Are you talking about primary summation or partial sums which I mentioned? $\endgroup$ – tejasvi88 Jun 7 '18 at 13:14
  • $\begingroup$ @GEdgar Sorry, I didn't get your point. Are you referencing WolframAlpha? Or, are you suggesting to check my final expression with substitution? To clarify, I've yet not simplified the original summation. I'm still stuck in finding above mentioned partial sums. $\endgroup$ – tejasvi88 Jun 7 '18 at 13:18
2
$\begingroup$

If we do as you suggest and break the sum into $$ \sum_{k< n/2} (n-2k)\binom nk + \sum_{k>n/2} (2k-n)\binom nk $$ (for $k=n/2$, if such a term exists, we have $|2k-n|=0$, so we can drop it) then we have $$ n\left(\sum_{k < n/2} \binom nk - \sum_{k>n/2}\binom nk\right) + 2\left(\sum_{k>n/2} k\binom nk - \sum_{k< n/2} k\binom nk\right). $$ The first sum simplifies to $0$ by symmetry of the binomial coefficient.

For the second sum, we can rewrite $$k\binom nk = k \cdot \frac{n!}{k!\,(n-k)!} = \frac{n!}{(k-1)!\,(n-k)!} = n \cdot \frac{(n-1)!}{(k-1)!\,(n-k)!} = n \binom{n-1}{k-1}.$$ This turns an annoying dependence on $k$ into a dependence on $n$ which we can simply factor out, getting $$ 2n \left(\sum_{k>n/2} \binom{n-1}{k-1} - \sum_{k<n/2} \binom{n-1}{k-1}\right). $$ Here, as before, most terms cancel, but we get something left over near the middle, because the two sums are no longer perfectly symmetric. The first term of the first sum is $\binom{n-1}{\lfloor n/2\rfloor}$ which does not cancel with anything; all other terms of the first sum cancel with symmetric terms of the second sum. (The second sum has one less term because when $k=0$, $k\binom nk=0$, so we begin that sum at $k=1$ to avoid dealing with a weird $n\binom{n-1}{-1}$ term.) Thus, our final answer is $$ 2n \binom{n-1}{\lfloor n/2\rfloor}. $$

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