Bounds on expected difference in coin toss sequence For any sequence of T fair coin flips, let $N_h, N_t$ be the number of heads and tails in the sequence.
I'm supposed to find asymptotically tight upper and lower bounds on $\mathbb{E}[|N_h - N_t|]$. 
Now due the 'any sequence' I'm inclined to say $0 \leq \mathbb{E}[.] \leq T$. Both bounds will have a small probability of $\frac{1}{2^T}$ of happening (if T is even). 
However, I am not certain this is the right approach. 
Using $N_t = T - N_h$ results in $\mathbb{E}[|2N_h - T|]$. 
Could use Jensen's inequality, $\mathbb{E}[|2N_h - T|] \geq |2\mathbb{E}[N_h] - T| = 0$. 
 A: You can actually compute this expectation exactly.
Consider the simpler case that we toss $2n$ coins. Then we have
$$
E[|N_h - N_t|]=E[|2 N_h - 2n|] = E[2 N_h - 2n; N_h>n]+E[2 N_t - 2n; N_t>n]
=2 E[2 N_h - 2n ; N_h>n] = 2 \frac{1}{2^n}\sum_{m > n} \binom{2n}{m}(2m-2n)=2^{1-2 n} (n+1) \binom{2 n}{n+1} \sim \frac{2 \sqrt{n}}{\sqrt{\pi }}.
$$

More details:
To see that
$$
\sum _{m=n+1}^{2 n} 2 (m-n) \binom{2 n}{m}
=\sum _{k=1}^n 2 k \binom{2 n}{k+n}
=
(n+1) \binom{2 n}{n+1}
$$
one can check that
$$
2 k \binom{2 n}{k+n}=\Delta _k(-(k+n) \binom{2 n}{k+n})
$$
where
$$
\Delta_k(f(n,k))=f(n,k+1)-f(n,k).
$$
The asymptotic approximation comes from Stirling's approximation.

There is also a combinatorial proof of
$$
\sum _{k=1}^n 2 k \binom{2 n}{k+n}
=
(n+1) \binom{2 n}{n+1}
$$
Consider a bit string of length $2n$ with $n+k$ $1$'s and $n-k$ $0$'s. If we write the first $n$ bits and the second $n$ bits as a $2$ by $n$ matrix, there are $k$ columns with two $1$. Chose a $1$ in these $k$ columns and mark it. Keep the row with the mark unchanged, but turn the other row to be the XOR of both rows, except at this marked column. These gives a bit string of length $2n$ with $n+1$ $1$'s. An example of $n=5$ and $k=2$ would be
$$
11011\\
1010\bf{1}
$$
turns into
$$
01011\\
1010\bf{1}
$$
So the LHS of the equation we have to prove counts the number of such strings, as the RHS.
