Let be a sequence of iid Bernoulli distributed random variable with for

Then is binomially distributed with parameters and is binomially distributed with parameters . It is evident that and are independent.

Now realize that is binomially distributed with parameters .

This spares you any computations.

I believe it's called the Poisson Binomial Distribution: https://math.stackexchange.com/questions/1153576/addition-of-two-binomial-distribution

Here is a (surprising) proof using Cauchy-Schwarz and "rearrangement". The following lemma will be the key. · Lemma · : Let $X,Y$ be independent integer-valued rvs, then \begin{align*} · (a)\; &\mbox{ for any } z: \;\mathbb{P}(X+Y=z)^2\leq \big(\sum_x\mathbb{P}(X=x)^2\big)\,\big(\sum_y \mathbb{P}(Y=y)^2\big)\\ · (b)\; &\sum_z\mathbb{P}(X-Y=z)^2=\sum_z\mathbb{P}(X+Y=z)^2\end{align*}Proof: (a) apply Cauchy-Schwarz to · $\mathbb{P}(X+Y=z)=\sum_x \mathbb{P}(X=x)\mathbb{P}(Y=z-x)$ · (b) let $(X^\prime,Y^\prime)$ be distributed as $(X,Y)$, and independent of . Then · \begin{align*} · \sum_z\mathbb{P}(X-Y=z)^2=\mathbb{P}(X-Y=X^\prime-Y^\prime)=\mathbb{P}(X-X^\prime=Y-Y^\prime)\\ · \sum_z\mathbb{P}(X+Y=z)^2=\mathbb{P}(X+Y=X^\prime+Y^\prime)=\mathbb{P}(X-X^\prime=Y^\prime-Y) · \end{align*} · Since $Y-Y^\prime$ and $Y^\prime-Y$ are identically distributed, and independent of $(X,X^\prime)$ the right hand sides above are equal. End Proof · Now to your question above. Let $n=2m$. We have to show that · \begin{align*} \mathbb{P}(X_k+Y_{2m-k}=\ell)\leq \mathbb{P}(X_m+Y_m=m)\end{align*}For the right hand side above we have (using 1. below) · \begin{align*} \mathbb{P}(X_m+Y_m=m)=\mathbb{P}(X_m=X_m^\prime)=\sum_l \mathbb{P}(X_m=l)^2\end{align*} · To transform the left hand side, observe that well known properties of the binomial distribution give: · \begin{align} 1.\; &Y_k \mbox{ is distributed as}\; k-X^\prime_k, \mbox{where $X_k^\prime$ is distributed as $X_k$,}\\&\mbox{ and independent of $X_k$}\\ · 2.\; &\mbox{ $X_{m+j}$ resp. $Y_{m+j}$ are distributed as $X_m+X_j$ resp. $Y_m+Y_j$, where}\\ · &\mbox{ the summands are independent} · \end{align} · Using 1. gives that $\sum_l \mathbb{P}(X_m=l)^2=\sum_l \mathbb{P}(Y_m=l)^2$ and further that · $$ \mathbb{P}(X_k+Y_{2m-k}=\ell)=\mathbb{P}(X_{2m-k}+Y_k=2m-\ell)\;,$$ so we may w.l.o.g. assume that $k\leq m$. · Using 1. and 2. we have · $$\mathbb{P}(X_k+Y_{2m-k}=\ell)=\mathbb{P}(X_k-X_{m-k}+Y_m=\ell+k-m)$$ · where $X_k,X_{m-k}$ and $Y_m$ on the right hand side are independent. · Using part (a) of the lemma (with $X=X_{k}-X_{m-k}$ and $Y=Y_m$) · gives $$\mathbb{P}(X_k+Y_{2m-k}=z)^2 \leq \big(\sum_x \mathbb{P}(X_k-X_{m-k}=x)^2\big)\big(\sum_y\mathbb{P}(Y_m=y)^2\big)$$ · Finally using part (b) of the lemma on the first factor gives · $$\sum_{x}\mathbb{P}(X_k-X_{m-k}=x)^2=\sum_x\mathbb{P}(X_k+X_{m-k}=x)^2=\sum_x\mathbb{P}(X_m=x)^2$$ · so that ultimately · $$\mathbb{P}(X_k+Y_{n-k}=z)^2\leq \big(\sum_x \mathbb{P}(X_m=x)^2\big)\big(\sum_y\mathbb{P}(Y_m=y)^2\big)=\big(\sum_x \mathbb{P}(X_m=x)^2\big)^2\;,$$ · as desired.

It will be a special case of the Poisson Binomial Distribution.