5

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*}

math110
  • 93,304
  • You can use the $\binom{n}{k} = \binom{n}{n-k}$ to deal with the terms inside brackets further ! – r9m Dec 28 '14 at 03:53
  • 1
    meaning that $\sum_{k=0}^{[n/2]}\binom{n}{k}=\sum_{k=[n/2]+1}^{n}\binom{n}{k}?$ – math110 Dec 28 '14 at 03:54
  • now do $\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$ and use the same thing as before ! :) – r9m Dec 28 '14 at 04:00
  • @r9m,But if you this,and then you will take reslut by $=0$? – math110 Dec 28 '14 at 04:05
  • I leave it to your fair judgement ! thank you :-) – r9m Dec 28 '14 at 04:10
  • 1
    possible duplicate of A finite sum over $\pm 1$ vectors – Aryabhata Dec 28 '14 at 04:29
  • 1
    @Aryabhata Its not a duplicate ! They might involve the same identity but the question statements are entirely different. – r9m Dec 28 '14 at 04:41
  • 1
    @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
  • @Aryabhata I am not sure if I can call the linked question a more canonical or general scenario of this OP. So I'm not sure if I can call it an 'abstract dupe'. It's true they are just 'minor variants' though. :) – r9m Dec 28 '14 at 21:52
  • 1
    @r9m: Yes, minor variants for sure (one of the primary reasons the whole abstract dupes things was started). – Aryabhata Dec 29 '14 at 03:10

2 Answers2

9

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

Brian M. Scott
  • 616,228
8

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

Did
  • 279,727
Sangchul Lee
  • 167,468
  • 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 – math110 Dec 28 '14 at 04:13
  • 2
    @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 04:24
  • Oh, Now I understand,Thank You +1 – math110 Dec 28 '14 at 04:27
  • 1
    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 03 '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 03 '15 at 12:06