Finding $\sum\limits_{k=0}^n|2k-n|\times\binom nk$

239 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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