# How find this sum $\sum_{k=0}^{n}\binom{n}{k}|n-2k|$ closed form or asymptotic behaviour?

Find the following series closed form or asymptotic behaviour

$$\dfrac{\displaystyle \sum_{k=0}^{n}\binom{n}{k}|n-2k|}{2^n}$$

I use wolfram can't give the closed form: see wolfram ,so I think maybe can find the asymptotic expansion?

I think this problem is equivalent find following closed( or asymptotic behaviour) \begin{align*} &\sum_{k=0}^{[n/2]}\binom{n}{k}(n-2k)+\sum_{k=[n/2]+1}^{n}\binom{n}{k}(2k-n)\\ &=n\left(\sum_{k=0}^{[n/2]}\binom{n}{k}-\sum_{k=[n/2]+1}^{n}\binom{n}{k}\right)-2\left(\sum_{k=1}^{[n/2]}k\binom{n}{k}-\sum_{k=[n/2]+1}^{n}k\binom{n}{k}\right)\\ &=-2\left(\sum_{k=1}^{[n/2]}k\binom{n}{k}-\sum_{k=[n/2]+1}^{n}k\binom{n}{k}\right)\\ \end{align*}

• meaning that $\sum_{k=0}^{[n/2]}\binom{n}{k}=\sum_{k=[n/2]+1}^{n}\binom{n}{k}?$ – china math Dec 28 '14 at 3:54
• possible duplicate of A finite sum over $\pm 1$ vectors – Aryabhata Dec 28 '14 at 4:29
• @Aryabhata Its not a duplicate ! They might involve the same identity but the question statements are entirely different. – r9m Dec 28 '14 at 4:41
• @r9m: Think of it as an abstract dupe. So what if this question is missing the context? The idea of closing as dupe is to keep the answers in one place (or at least point to other such answers). In this case, I think it is a valid reason. If the community does not think so, the close vote will decay... – Aryabhata Dec 28 '14 at 21:44
• @r9m: Yes, minor variants for sure (one of the primary reasons the whole abstract dupes things was started). – Aryabhata Dec 29 '14 at 3:10

Here is a very basic asymptotic behavior: Let $X_{1}, X_{2}, \cdots$ be i.i.d. symmetric Bernoulli trials with $\Bbb{P}(X_{i} = 1) = \Bbb{P}(X_{i} = -1) = 1/2$. Then for $S_{n} = X_{1} + \cdots + X_{n}$ we have

$$\frac{1}{2^{n}} \sum_{k=0}^{n} \binom{n}{k} |n - 2k| = \Bbb{E}|S_{n}|.$$

From the central limit theorem, it follows that $S_{n}/\sqrt{n} \Rightarrow Z$ for a standard normal random variable $Z \sim \mathcal{N}(0, 1)$. So we have the following asymptotic relation

$$\Bbb{E}|S_{n}| \sim \sqrt{n}\, \Bbb{E}|Z| = \sqrt{\frac{2n}{\pi}}.$$

• Nice.but can you expalin why $E|(2S_{n})|=\dfrac{1}{2^n}\sum_{k=0}^{n}\binom{n}{k}|n-2k|$? detail? especial this form $|n-2k|$ how to have this – china math Dec 28 '14 at 4:13
• @chinamath: Flip a fair coin $n$ times. Count a head as $+1$ and a tail as $-1$. Then $2S_n$ is the number of heads minus the number of tails. The possible values are $-n,-n+2,\ldots,n-2,n$, i.e., the numbers $n-2k$ for $k=0,\ldots,n$. In fact, $2S_n=n-2k$ when you get $k$ tails, and the probability of $k$ tails is $\frac1{2^n}\binom{n}k$. – Brian M. Scott Dec 28 '14 at 4:24
• Oh, Now I understand,Thank You +1 – china math Dec 28 '14 at 4:27
• Convergence in distribution does not imply the convergence of the expectations without a supplementary condition. Fortunately, in the present case the fact that $(S_n/\sqrt{n})$ is bounded in $L^2$ is such a supplementary condition. – Did Jan 3 '15 at 11:49
• @Did, You're right... since the absolute value function is not bounded, we need to appeal to some extra condition satisfied by our choice of $S_{n}$. Thank you for reminding that fact! – Sangchul Lee Jan 3 '15 at 12:06

\begin{align*} \sum_{k=0}^n\binom{n}k|n-2k|&=2\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}k(n-2k)\\\\ &=2\left(n\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}k-2\sum_{k=0}^{\lfloor n/2\rfloor}k\binom{n}k\right)\\\\ &=2n\left(\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}k-2\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-1}{k-1}\right)\\\\ &=2n\left(\sum_{k=0}^{\lfloor n/2\rfloor}\left(\binom{n}k-\binom{n-1}{k-1}\right)-\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-1}{k-1}\right)\\\\ &=2n\left(\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-1}k-\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-1}{k-1}\right)\\\\ &=2n\left(\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-1}k-\sum_{k=0}^{\lfloor n/2\rfloor-1}\binom{n-1}k\right)\\\\ &=2n\binom{n-1}{\lfloor n/2\rfloor}\;. \end{align*}

It doesn’t matter whether $n$ is odd or even: if $n$ is even, the $k=\frac{n}2$ term is zero anyway.

• It is nice! Of course, (+1) – Sangchul Lee Dec 28 '14 at 4:16
• It's Nice too!+1 – china math Dec 28 '14 at 4:17
• @chinamath I think I left enough hint in the comments to complete the answer by yourself ! :-) – r9m Dec 28 '14 at 4:22
• I forget the last $\binom{n-1}{k}$ not $\binom{n}{k}$,so must leave a term – china math Dec 28 '14 at 4:25
• +1. Pretty nice and cumbersome. I was following another way: By expressing the binomial as a contour integral which right away becomes quite ugly such that I left it altogether. – Felix Marin Jan 1 '15 at 23:31