Average absolute value of sum with Rademacher random variables Let $a_1, \ldots, a_n $ be independent Rademacher random variables with distribution $P(a_i=1) = P(a_i=-1) = \frac 12$. Estimate from below $$E \left|\sum_{i=1}^n a_i\right|.$$ 
I've reduced this problem to the next one (for even $n$):
Estimate from below following $$\frac 1{2^{n-1}} \left(\sum_{k=n/2}^n kC_n^k - \sum_{k=0}^{n/2}kC_n^k\right).$$
 A: We don't need to estimate it ... we can find the exact solution.
If $Z$~Bernoulli($\frac12$), then $X=2Z-1$ has a Rademacher distribution where $X=-1$ or $1$ with equal probability. Let $X_1, ..., X_n$ denote indepedent Rademacher random variables. Then, the pmf of:
$$ \sum_{i=1}^n X_i  =  (2 \sum_{i=1}^n Z_i) - n = 2 Y -n$$
where $Y$~ $Binomial(n,\frac12)$ (since the sum of $n$ Bernoulli's is $Binomial(n,p)$). 
Let random variable $Y$ have pmf $f(y)$:

Then, the expectation we seek, namely, $E[ \left|  \sum_{i=1}^n X_i \right|]$ can be found as $E[ \left|  2 Y - n \right|]$, derived here using mathStatica (of which I am one of the authors):

All done.
Here is a plot of the solution as $n$ increases from 1 to 100:


Monte Carlo check
When using computer algebra systems (or indeed working manually), it is always good practise to check one's work using alternative methods. For example, when $n = 130$, the exact solution derived above yields:
sol /. n -> 130.


9.07981

Here is a quick Monte Carlo 'check' in Mathematica  ... when $n = 130$, we generate 100000 samples, each containing the sum of 130 Rademacher random variables, sum them up, take the absolute value, and compute the sample mean:
Mean[Table[ 
              Abs[Total[Table[RandomChoice[{-1, 1}], {130}]]], 
           {100000}]] // N


9.07358

:)
