How to prove the bound on the probability? I am trying to prove, given a random sequence of $2k$ bits, the probability that the sequence contains exactly $k$ ones is less than or equal to $1/2$.
I tried
${2k \choose k}/{2^{2k}}=\dfrac{(2k)!}{k!k!2^{(2k)}}=\dfrac{\prod\limits_{i=1}^k (k+i)}{4^kk!}=\prod\limits_{i=1}^k \dfrac{k+i}{4i}$.
Then i got stuck.
 A: Let $X=\{0,1\}^{2k}$ be the space of all binary sequences over $\{0,1\}$. This is a vector space over the field with two elements, which I'll denote by $F_2$.
The subset of $X$ consisting of all binary subsets with exactly $k$ ones is contained in the space:
$$
Y=\{x=(x_i)_{i=1}^k\in X : \sum_i x_i =k \; in \; F_2\}
$$
If $k$ is even, then $Y$ is a subspace of $X$ which is not all of $X$, thus has dimension at most $k-1$. If $k$ is odd, then all the elements of the form $y+(1,0,...,0)$ form a subspace of $X$ of dimension at most $k-1$. In both cases, one finds that:
$$
\#\{binary\; sequences\; with \; k\; ones\}\le|Y|\le2^{k-1}
$$
Which implies:
$$
Prob(random \; binary \; sequence\;has\;k\;ones)\le \frac{2^{k-1}}{2^k}=\frac{1}{2}
$$
A: It suffices to show that the number of ways to get exactly $k$ ones is no greater than the number of ways to get either $k-1$ or $k+1$ ones. We use relationships in Pascal's triangle.
\begin{eqnarray*}
\text{#Ways to get $k$ ones} &=& \binom{2k}{k} \\
&=& \binom{2k-1}{k-1} + \binom{2k-1}{k} \qquad\text{(going up one level in the triangle)}\\
&\leq& \binom{2k}{k-1} + \binom{2k}{k+1} \qquad\text{(going back down one level)}\\
&=& \text{#Ways to get $k-1$ or $k+1$ ones.}
\end{eqnarray*}
