<s>[INST] Expected Value of |H-T| A coin is flipped $n$ times, with $H$ heads and $T$ tails. What is the expected value of $|H-T|$?
Here's where I'm at so far:
There are $2^n$ total different flip sequences. Each is equally likely. Thus the expected value is the sum of all the $|H-T|$ values for each flip divided by $2^n$. We can sort these flip sequences by the value of $H$. Given $n$ flips, the number of sequences with $H$ heads is ${n\choose H} = \frac{n!}{(n-H)!H!}$. The sum therefore is $\sum\limits_{i=0}^{n} \frac{n!}{(n-H)!H!} |H-T|.$
This did not really get me anywhere, so I started to evaluate it numerically. I wrote up some python code to calculate it for $n$, and came up with the following sequence (starting with $1$ flip):
$1, 1, \frac32, \frac32, \frac{15}{8}, \frac{15}{8}, \frac{35}{16},\frac{35}{16}\dots$. According to Wolfram Alpha, the general term for this sequence is $a_{n+2} = a_n + \frac{a_{n+1}}{n+1}$, which holds for the first 10000 terms calculated by my program, so I am fairly confident that this is in fact the general formula. I just need to prove it.
Any help would be much appreciated. This seems like a fairly basic statistical property since it seems so related to standard deviation so I am surprised that my scourings of the internet have not gleaned results.
 [/INST] Let $a_n = \operatorname{E}[|H-T|] = \operatorname{E}[|2H - n|]$ for $H \sim \operatorname{Binomial}(n,1/2)$ and $T = n - H$.  Then we first observe from your sequence that $a_{2m} = a_{2m-1}$ for each positive integer $m$.  So let's aim to prove this property first.  Note
$$\begin{align}
a_{2m} &=  \frac{1}{2^{2m}} \sum_{h=0}^{2m} | 2h - 2m | \binom{2m}{h} \\
&= \frac{1}{2^{2m-1}} \sum_{h=0}^{2m} |h - m| \left(\binom{2m-1}{h-1} + \binom{2m-1}{h}\right) \\
&= \frac{1}{2^{2m-1}} \left( \sum_{h=1}^{2m} |h - m| \binom{2m-1}{h-1}   + \sum_{h=0}^{2m-1} |h-m| \binom{2m-1}{h} \right) \\
&= \frac{1}{2^{2m-1}} \sum_{h=0}^{2m-1} \bigl(|h - (m-1)| + |h - m| \bigr)\binom{2m-1}{h} \\
&= \frac{1}{2^{2m-1}} \sum_{h=0}^{2m-1} |2h - (2m-1)| \binom{2m-1}{h} \\
&= a_{2m-1},
\end{align}$$
where the penultimate step holds because
$$|h-(m-1)| + |h-m| = \begin{cases} 2m-1 - 2h, & 0 \le h \le m-1 \\
2h-2m+1, & m \le h \le 2m-1.\end{cases}$$  The only case where equality is violated is if $m-1 < h < m$, but this is not possible since $h, m$ are integers.
So it suffices to consider the case where $n$ is, say, even.  Then we have
$$\begin{align}
a_{2m} &= \frac{1}{2^{2m-1}} \sum_{h=0}^{2m} |h-m| \binom{2m}{h} \\
&= \frac{1}{2^{2m-2}} \sum_{h=0}^m (m-h) \binom{2m}{h} \\
&= \frac{1}{2^{2m-2}} \left( m \sum_{h=0}^m \binom{2m}{h} - \sum_{h=0}^m h \binom{2m}{h}\right) \\
&= \frac{1}{2^{2m-2}} \left( \frac{m}{2}\left( \binom{2m}{m} + \sum_{h=0}^{2m} \binom{2m}{h} \right) - \sum_{h=1}^m \frac{(2m)!}{(h-1)!(2m-h)!} \right) \\
&= \frac{1}{2^{2m-2}} \left( \frac{m}{2} \binom{2m}{m} + 2^{2m-1} m - 2m \sum_{h=1}^m \binom{2m-1}{h-1}\right) \\
&= \frac{m}{2^{2m-1}} \left( \binom{2m}{m} + 2^{2m} - 4 \sum_{h=0}^{m-1} \binom{2m-1}{h} \right) \\
&= \frac{m}{2^{2m-1}} \left( \binom{2m}{m} + 2^{2m} -  2\sum_{h=0}^{2m-1} \binom{2m-1}{h} \right) \\
&= \frac{m}{2^{2m-1}} \left( \binom{2m}{m} + 2^{2m} - 2(2^{2m-1}) \right) \\
&= \frac{m}{2^{2m-1}} \binom{2m}{m}.
\end{align}$$
This was a quick and dirty proof--I don't like the computation for $a_{2m}$ because I strongly suspect there is a much more simple and elegant way to obtain this result, but this was the first thing that came to mind.
</s>