How prove this $|S_{1}|-|S_{2}|\le 2^{2n}\binom{2n}{n}$ Question:

Let $n\in \mathbf N^{+}$,and define set $S=\{1,2,\cdots,4n\}$, for any $ a<b\in \mathbf R^{+}$, define
$$S_{1}=\{\,X\mid X\subseteq S,a\le S(X)\le b,S(X)\equiv 1\pmod 2\,\}$$
$$S_{2}=\{\,X\mid X\subseteq S,a\le S(X)\le b,S(X)\equiv 0\pmod 2\,\}$$
where $$S(X)=a_{1}+a_{2}+\cdots+a_{k}\text{ for }X=\{a_{1},a_{2},\cdots,a_{k}\}$$

Show that
$$|S_{1}|-|S_{2}|\le 2^{2n}\binom{2n}{n}$$
where $|S_{1}|$ is number of the set element
$S_{1}$.
Maybe can use
$$\binom{2n}{n}=\dfrac{(2n)!}{n!\cdot n!}=\dfrac{2^n\cdot(2n)!!}{(n!)^2}$$
then I can't. It is said this problem is not hard, but I can't prove this.
Maybe this post is useful?
Thank you
 A: The two sets are disjoint, $S_1 \cap S_2 = \varnothing$ since $S(X)$ will be either even or odd.  
Notice that if $a < 1, b > 4n$, then $|S_1| = |S_2|$.
We are more likely to get these large differences when we fix the value of $S(X)=c$, in which case $|S_1|=0$ or $|S_2|=0$ and we bound the size of the non-empty set.
Let $S(X) = S(E_0) + S(O_0)$ where $E\subseteq X$ is the subset of even elements and $O \subseteq X$ are the odd elements.


*

*The even numbers $E = \{ 2,4,6,\dots, 4n \}$ will not affect the parity of $S(X)$ - so let's just put any of the $2^{2n}$ subsets $E_0 \subseteq E$ there, and let their sum be $S(E_0)$.

*Only the odd numbers $O = \{ 1,3,\dots, 4n-1\}$ will affect the parity.  Once we fix a collection of even numbers, the sum of the remaining odd numbers should be
$S(O)=c - S(E)$.  How many possible subsets are there?

Proposition Let's show that for any $2n$ numbers at most $\binom{2n}{n}$ subsets can have the same sum.
Let's prove this by induction:


*

*$n=1$, we have two numbers $\{ a_1, a_2\}$.  There can be at most two $\binom{2}{1}$ subsets $X$ with the same $S(X)$, if $a_1 = a_2$, and none if $a_2 > a_1$.

*Assume for $n=k$, the induction hypothesis holds $\displaystyle \max_{1 \leq c \leq 4n} |\{X: S(X)=c\}| \leq \binom{2k}{k} $.

*If we include a new element $a_{k+1}$, there can be at most $ 2 \binom{2k}{k} < \binom{2k+2}{k+1}$ subsets $X$ with the same value of $S(X)$.



This sounds like an olympiad problem and I took way more than the allotted time.  Maybe there is a neater proof using probabilistic method.
Let $X \subseteq S$ be a random set with $\mathbb{P}[i \in X] = \frac{1}{2}$ so that each set occurs with probability $2^{-2n}$.
There are two events to consider:


*

*$a \leq S(X) \leq b$

*$S(X)$ is an even or odd number


In terms of probabilities, our two subsets could be written 


*

*$2^{-2n}|S_1| = \mathbb{P}\big[ a \leq S(X) \leq b \bigwedge S(X) \equiv 1 \mod 2\big]$

*$2^{-2n}|S_2| = \mathbb{P}\big[ a \leq S(X) \leq b \bigwedge S(X) \equiv 0 \mod 2\big]$


We were asked to bound the probability of these two events occurring:
$$ \frac{|S_1|-|S_2|}{2^{2n}}  \leq \frac{1}{2^{2n}}\binom{2n}{n}$$
In fact we showed that fixing $S(X)=c$ determines the parity of $S(X)$:
\begin{eqnarray*} \mathbb{P}\big[ S(X)=c  \bigwedge S(X) \equiv 1 \mod 2\big]
&=& \mathbb{P}\big[S(X) \equiv 1 \mod 2  \big|S(X)=c \big]
\mathbb{P}\big[  S(X) = c \big] \\
&=&  \left\{ \begin{array}{cc} \mathbb{P}\big[  S(X) = c \big] & c \text{ is odd} \\
0 & c \text{ is even} \end{array}\right.
\end{eqnarray*}

It remains to estimate that $\mathbb{P}[S(X) = c] \leq \frac{1}{2^{2n}}\binom{2n}{n}$.
We oserved that $S(X) = S(X_1)+S_2(X_2)$ splitting into even and odd parts.
\begin{eqnarray}  \mathbb{P}\big[ S(X)=c  \bigwedge S(X) \equiv 1 \mod 2\big]
 &=& \mathbb{P}\big[ S(X_1)=c- S(X_2)   \bigwedge S(X_1) \equiv 1 \mod 2\big] \\ 
 &\leq &  \sum_{X_2 \subseteq \{ 2,4,\dots, 2n\}} \mathbb{P}[X_2] \mathbb{P}\big[ S(X_1)=c- S(X_2)  | X_2\big] \\
& \leq & \sum_{X_2} \mathbb{P}[X_2]  \cdot \frac{1}{2^{2n}} \binom{2n}{n} \\
& = & \frac{1}{2^{2n}} \binom{2n}{n}
\end{eqnarray}
Which is the same estimate as before.

For a different starting point, look at the lecture notes on partitions by the man himself, Herbert Wilf.
