For natural $n$, let
\begin{equation}
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}
\end{equation}
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](https://mathoverflow.net/a/450578/36721).



On a double sum involving binomial coefficients
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:
\begin{equation}
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}
\end{equation}
In particular, $p\_n \leq 1/2$ for all $n$.


