Complicated sum with binomial coefficients

I know how to prove, that $\frac{1}{2^{n}}\cdot\sum\limits_{k=0}^nC_n^k \cdot \sqrt{1+2^{2n}v^{2k}(1-v)^{2(n-k)}}$ tends to 2 if n tends to infinity for $v\in (0,\, 1),\ v\neq 1/2$. This can be proved with the use of Dynamical systems reasonings, which are non-trivial and complicated. Is there quite good combinatiorial proof of this fact? How would you solve this problem as it is? Here $C_n^k$ denotes $\frac{n!}{k!(n-k)!}$.

Solution 1:

You can rewrite the expression as $$ \sum_{k=0}^n \sqrt{P_{1/2,n}(k)^2 + P_{v,n}(k)^2}, $$ where $P_{a,n} = {n\choose k} a^k (1-a)^k = P\big(\mathrm{Binom}(n,a) = k\big)$ is the binomial distribution with parameters $n$ and $a\in(0,1)$.

Now the statement is pretty clear, since by the law of large numbers the distributions $P_{1/2,n}$ and $P_{v,n}$ "sit" on disjoint sets: $P_{1/2,n}$ concentrates around $n/2$, $P_{v,n}$, around $nv$. Therefore, $\sqrt{P_{1/2,n}(k)^2 + P_{v,n}(k)^2}\approx P_{1/2,n} $ for $k\approx n/2$, and $\sqrt{P_{1/2,n}(k)^2 + P_{v,n}(k)^2}\approx P_{v,n} $ for $k\approx nv$, so the whole sum is $\approx \sum_{k\approx n/2} P_{1/2,n} + \sum_{k\approx nv} P_{v,n} \approx 1+ 1 = 2$.

Formally, assuming wlog that $v<1/2$ and taking any $b\in (v,1/2)$, $$ 2\ge \sum_{k=0}^n \sqrt{P_{1/2,n}(k)^2 + P_{v,n}(k)^2} \ge \sum_{k\le nb} P_{v,n}(k) + \sum_{k > nb} P_{1/2,n}(k) \\ = 2 - \sum_{k> nb} P_{v,n}(k) - \sum_{k\le nb} P_{1/2,n}(k) = 2 - P\big(\mathrm{Binom}(n,v) \ge nb\big) - P\big(\mathrm{Binom}(n,1/2) < nb\big) \\ \ge 2 - P\big(|\mathrm{Binom}(n,v)-nv| \ge n(b-v)\big) - P\big(|\mathrm{Binom}(n,1/2)-n/2| \ge n(1/2-b)\big) \\\ge 2 - \frac{v(1-v)}{n(b-v)^2} - \frac{1}{4n(1/2-b)^2}, $$ where the last is by Chebyshev's inequality. Hence the result follows.

Note that by using some stronger result (Chernoff, Hoeffding, Bernstein) it is easy to show that the convergence is exponentially fast.

Solution 2:

Let $$x=\sqrt[4]{4^nv^{2k}(1-v)^{2n-2k}}=(\sqrt{2})^n (\sqrt{v})^{k}(\sqrt{1-v})^{n-k},x>0$$ First, we have following inequality $$x^2-x+1<\sqrt{x^4+1}<x^2+1,x>0\tag{1}$$ because $$x^4+1>(x^2-x+1)^2\Longleftrightarrow x(2x^2-3x+2)>0,x>0$$ $$(x^4+1)<(x^2+1)^2\Longleftrightarrow x^2>0$$ use $(1)$, we have $$1+2^nv^k(1-v)^{n-k}-(\sqrt{2})^n(\sqrt{v})^k(\sqrt{1-v})^{n-k} <\sqrt{1+4^nv^{2k}(1-v)^{2n-2k}}<1+2^nv^k(1-v)^{n-k}\tag{2}$$ use $(2)$,For one thing,we have \begin{align*}\lim_{n\to\infty}\dfrac{\displaystyle\sum_{k=0}^{n}\binom{n}{k}\sqrt{1+4^nv^{2k}(1-v)^{2n-2k}}}{2^n} &<\lim_{n\to+\infty}\dfrac{\displaystyle\sum_{k=0}^{n}\binom{n}{k}(1+2^nv^{k}(1-v)^{n-k})}{2^n}\\ &=\lim_{n\to+\infty}\dfrac{\displaystyle\sum_{k=0}^{n}\binom{n}{k}+\sum_{k=0}^{n}\binom{n}{k}2^nv^k(1-v)^{n-k}}{2^n}\\ &=\lim_{n\to+\infty}\dfrac{(1+1)^n+2^n(v+1-v)^n}{2^n}\\ &=2 \end{align*} use $(2)$,on the other hand $$\lim_{n\to\infty}\dfrac{\displaystyle\sum_{k=0}^{n}\binom{n}{k}\sqrt{1+4^nv^{2k}(1-v)^{2n-2k}}}{2^n} >2-\lim_{n\to+\infty}\dfrac{(\sqrt{2v}+\sqrt{2(1-v)})^n}{2^n}=2$$ because Use Cauchy-Schwarz inequality we have $$\sqrt{v}+\sqrt{1-v}<\sqrt{2(v+1-v)}=\sqrt{2}$$