# How to prove the sum of n squared binomial probabilities does not increase as n increases

Let $F\left( n \right) = \sum\limits_{k = 0}^n {{{\left( {C_n^k{p^k}{{\left( {1 - p} \right)}^{n - k}}} \right)}^2}}$, prove $F\left( n \right) \ge F\left( {n + 1} \right)$.

UPDATE: More general, denote $F\left( n \right) = \sum\limits_{k = 0}^n {C_n^kp_1^kq_1^{n - k}C_n^kp_2^kq_2^{n - k}}$, where ${q_1} = 1 - {p_1}$ and ${q_2} = 1 - {p_2}$, prove $F\left( n \right) \ge F\left( {n + 1} \right)$.

$\color{red}{^\bf{{\rm{New}}}}$ UPDATE: More general, denote $F\left( n \right) = \sum\limits_{k = 0}^n {C_n^kp_1^kq_1^{n - k}\sum\limits_{i = 0}^k {C_k^ip_2^iq_2^{k - i}C_{n - k}^{k - i}p_3^{k - i}q_3^{\left( {n - k} \right) - \left( {k - i} \right)}} }$, where $q_1=1-p_1$, $q_2=1-p_2$, and $q_3=1-p_3$, is it true that $F\left( n \right) \ge F\left( {n + 1} \right)$?

Denote $q=1-p$, write $[x^a]f(x)$ for a coefficient of $x^a$ in the polynomial (or Laurent polynomial) $f(x)$. We have $$F(n)=[1](px+q)^n(px^{-1}+q)^n=[1]((p^2+q^2)+qp(x+x^{-1}))^n=\\=(2\pi)^{-1}\int_{0}^{2\pi}((p^2+q^2)+qp(e^{it}+e^{-it}))^ndt.$$ The function $(p^2+q^2)+qp(e^{it}+e^{-it})=p^2+q^2+2pq\cos t$ is non-negative and its values do not exceed 1, thus the result.

I use the useful relation $[1]\varphi(x)=(2\pi)^{-1}\int_0^{2\pi} \varphi(e^{it})dt$ for any Laurent polynomial $\varphi$.

UPD. For the updated problem, use the same integral representation for $p=\sqrt{p_1p_2},q=\sqrt{q_1q_2}$. We need to check that $p+q\leqslant 1$, this follows from $p\leqslant (p_1+p_2)/2,$
$q\leqslant (q_1+q_2)/2.$

$$\sum\limits_{i = 0}^k {C_k^ip_2^iq_2^{k - i}C_{n - k}^{k - i}p_3^{k - i}q_3^{\left( {n - k} \right) - \left( {k - i} \right)}}=[t^k](tp_2+q_2)^k(tp_3+q_3)^{n-k}$$

About updated function $F(n)$. Denoting $h(z)=z^{-1}p_1(zp_2+q_2)+q_1(zp_3+q_3)$ we have $F(n)=[1](h(z))^n$, thus $$F(n)=\frac1{2\pi i}\int h(z)^ndz/z,$$ where integral is taken by any circuit around 0. It is natural to take the circuit with real value of $h(z)=p_1p_2+q_1q_3+q_1p_3 z+p_1q_2 z^{-1}$. The natural choice is the contour $z=\sqrt{\frac{p_1q_2}{q_1p_3}}e^{i\theta}$, we get $h(z)=p_1p_2+q_1q_3+2\sqrt{p_1q_1q_2p_3}\cos \theta$. We have $|h(z)|\leqslant p_1p_2+q_1q_3+p_1q_2+q_1p_3=p_1+q_1=1$, thus everything works nicely if we have $h(z)\geqslant 0$. This is not always the case. For example, if $p_2=q_3=0$ we get $h(z)=2\sqrt{p_1q_1}\cos \theta$ and the integral equals 0 for odd values of $n$ and is positive for even values of $n$. Needless to say, this could be seen from the very definition of $F(n)$, but for what it worth I leave here the general explanation.

• Thank you very much for your quick responds but please excuse me as a rookie. I didn’t quite follow you. Could you please give more details about how $[1]((p^2+q^2)+qp(x+x^{-1}))^n=(2\pi)^{-1}\int_{0}^{2\pi}((p^2+q^2)+qp(e^{it}+e^{-it}))^ndt$. Lots of thanks! – Jack Mar 10 '18 at 15:28
• Thanks for your explanation. Could you please kindly show some references or some keywords about the useful conclusion for Laurent polynomial that I can relate to? – Jack Mar 11 '18 at 3:34
• simply write $\varphi(x)=\sum_k a_k x^k$ and integrate, you get $(2\pi)^{-1}\sum_k a_k\int_0^{2\pi} e^{ikt}dt=a_0$. – Fedor Petrov Mar 11 '18 at 6:14
• A perfect answer! Thank you very much. – Jack Mar 14 '18 at 6:57
• Thank you so much for your excellent answer to the newest updated problem. Though I haven’t gone through the whole derivation yet because my limited mathematic knowledge, I verified the numerical equality between $F(n)$ and the proposed integral form using Matlab when p1, p2, and p3 were set to some specific values. I believe your answer is correct and I really appreciate it because it helps me a lot. I will keep working on it till I fully understand it. – Jack Apr 11 '18 at 13:31

$F(n)$ is the density maximum of the $n$th convolution power of a fixed (three point) probability density on $\mathbb Z$, and hence is decreasing in $n$.

To spell the first claim out, let $\ast$ indicate convolution products or powers of probability densities on $\mathbb Z$, let $\mathrm{b}_{n,p}$ denote the binomial density with the indicated parameters, $\mathrm{b}_p:= \mathrm{b}_{1,p}$ the Bernoulli density, and $q:=1-p$. Then $$F(n) = \sum_{k=0}^n \mathrm{b}_{n,p}(k) \mathrm{b}_{n,q}(n-k) = \big(\mathrm{b}_{n,p}\ast \mathrm{b}_{n,q}\big)(n) = \big(\mathrm{b}_p \ast \mathrm{b}_q\big)^{\ast n}(n) = \left\| \big(\mathrm{b}_p \ast \mathrm{b}_q\big)^{\ast n} \right\|_\infty .$$ To check the final step above, one may use the fact that convolutions of symmetric lattice unimodal laws are again symmetric unimodal (Wintner's theorem).

Of course, this is not shorter than Fedor's proof.

• Thanks a lot for your answer. I can see it’s also a great idea.Though I tired hard to understand your proof, given the fact that my major is not mathematics, I can’t figure it out. I really appreciate your brilliant idea you put here. – Jack Apr 12 '18 at 9:08