# On a double sum involving binomial coefficients

For natural $$n$$, let $$$$p_n:=2^{1-n}\sum_{v=1}^l \binom l{(v+l)/2}1(v\equiv l) \sum_{u=1-v}^{v-1}\binom k{(u+k)/2}1(u\equiv k), \tag{1}\label{1}$$$$ where $$k:=\lfloor(n+1)/2\rfloor$$, $$l:=\lfloor n/2\rfloor$$, and $$a\equiv b$$ means that $$a-b$$ is even.

Can this expression for $$p_n$$ be simplified? In particular, is it true that $$p_{4m+3}=1/2$$ for $$m=0,1,\dots$$? Is it true that $$p_n\le1/2$$ for all $$n$$?

A correct and complete answer to any one of these questions will be considered a correct and complete answer to this entire post.

The expression for $$p_n$$ in \eqref{1} was obtained in this previous answer.

The formula for $$p_n$$ was derived to be a probability relating two independent transformed binomials. In particular, $$p_n = \mathbb{P}(|U_n|<|V_n|)$$ where $$U_n = a_1 + \dots a_k \hspace{20pt} V_n = b_1 + \dots + b_l$$ and $$k = \lfloor (n+1)/2 \rfloor, l = \lfloor n/2 \rfloor$$.

When $$n=2m$$ then $$k = l = m$$ and so $$U_{2m}$$ and $$V_{2m}$$ are i.i.d. In this case we can exploit symmetry; $$\mathbb{P}(|U_n| < |V_n|) = \mathbb{P}(|V_n| < |U_n|)$$, and so we can write: $$p_{2m} = \frac{1}{2} \left ( 1 - \mathbb{P} ( |U_{2m}| = |V_{2m}| ) \right ).$$ In general, for discrete i.i.d. random variables $$X, Y$$ taking values in $$\mathbb{N}$$, we have: $$\mathbb{P}(X=Y) = \sum_{n = 0}^\infty \mathbb{P}(X = n)^2.$$ We can continue by splitting into two further cases depending on whether $$m$$ is even or odd, i.e. whether $$n$$ is $$0$$ or $$2$$ mod 4. The case $$n = 4m + 2$$ is easier; recall that $$U_{4m+2} \overset{d}{=} 2B_{2m+1} - (2m+1)$$, where $$B_{2m+1} \sim \text{Binomial}(2m+1,1/2)$$. So \begin{align} \mathbb{P}(|U_{4m+2}| = |V_{4m+2}| ) & = \sum_{p=0}^m \mathbb{P}(B_{2m+1} = (m-p) \text{ or } (m+p+1) )^2 \\ &= 2^{-4m} \sum_{p=0}^m {2m+1 \choose p}^2\\ &= 2^{-4m-1} {4m + 2 \choose 2m+1}. \end{align} The case $$n = 4m$$ is similar, but the probability is slightly different since one has to take into account the event $$\{|U_{4m}| = 0\}$$. Then we have: \begin{align} \mathbb{P}(|U_{4m}| = |V_{4m}|) &= 2^{-4m} \left ( {2m \choose m}^2 + 4 \sum_{p=0}^{m-1} {2m \choose p}^2 \right ) \\ &=2^{-4m} \left (2 {4m \choose 2m} - {2m \choose m}^2 \right). \end{align}

Now we have the case where $$n$$ is odd. $$U_n$$ and $$V_n$$ are not i.i.d, but instead $$U_n \overset{d}{=} V_n + a$$, where $$a$$ is an independent Rademacher. Let $$V_n'$$ be an i.i.d. copy of $$V_n$$. Then using the law of total probability we can write: $$p_n = \frac{1}{2} \left ( \mathbb{P}(|V_n+1| < |V_n'|) + \mathbb{P}(|V_n-1| < |V_n'|) \right ).$$

When $$n = 4m+3$$, $$V_n$$ is odd and in particular greater than 1 in absolute value. Thus, $$|V_n+a| \overset{d}{=} |V_n| + a$$ as adding a Rademacher will not change the sign of $$V_n$$. Then we have \begin{align} p_{4m+3} &= \frac{1}{2} \left ( \mathbb{P}(|V_n| + 1 < |V_n'|) + \mathbb{P}(|V_n| < |V_n'| + 1) \right ) \\ &= \frac{1}{2} \mathbb{P}(|V_n| \neq |V_n'| + 1)\\ &= \frac{1}{2} \end{align} since $$|V_n|$$ is always odd.

When $$n = 4m+1$$, $$V_n$$ is even and so once again the limiting factor is the event where $$V_n = 0$$. If we condition on the events where $$V_n$$ and $$V_n'$$ are zero and nonzero, respectively, we obtain the following expression: \begin{align} p_{4m+1} &= \mathbb{P}(V_n' \neq 0) \left (\mathbb{P}(V_n = 0) + \frac{1}{2} \mathbb{P}(V_n \neq 0) \right ) \\ &= \frac{1}{2}(1-\mathbb{P}(V_n = 0)^2) \\ &= \frac{1}{2} \left ( 1 - 2^{-4m} {2m \choose m}^2 \right ). \end{align}

Overall we have the following: $$$$p_{4m+k} = \begin{cases} \frac{1}{2} \left ( 1 - 2^{-4m} \left (2 {4m \choose 2m} - {2m \choose m}^2 \right) \right) & k = 0 \\ \frac{1}{2} \left ( 1 - 2^{-4m} {2m \choose m}^2 \right ) & k = 1\\ \frac{1}{2} \left ( 1 - 2^{-4m-1} {4m + 2 \choose 2m+1} \right) & k = 2\\ \frac{1}{2} & k = 3 \end{cases}$$$$ In particular, $$p_n \leq 1/2$$ for all $$n$$.

• Thank you for your answer. Can you write $n=4m+2$ and $n=4m$ instead of $n=4l+2$ and $n=4l$, since $l$ was already defined to be $\lfloor n/2 \rfloor$? Also, please do finish all the (four?) cases, and it would be good to have a (table?) summary of all the cases. Jul 11, 2023 at 19:51
• Also, $\displaystyle{\sum_{p=0}^l {2l+1 \choose 2p}^2}=\dfrac{2^{4 l+1} \Gamma \left(\frac{1}{2} (4 l+1)+1\right)}{\sqrt{\pi } (2 l+1)!}$. Jul 11, 2023 at 19:56
• @IosifPinelis I have changed the indices from $l$ to $m$ as requested. I also simplified the sum of binomial coefficients to say $p$ instead of $2p$, but this doesn't actually change the sum itself. WolframAlpha says apparently that this sum is equal to $\frac{1}{2}{4m+2 \choose 2m+1}$, interestingly. Jul 12, 2023 at 11:00
• Thank you once again! Jul 12, 2023 at 15:40