# Sum of squares of power of two sums and differences

What is the sum $$\sum\left(\frac12-\frac1{2^n}\pm\frac14\pm\frac18\pm\ldots\pm\frac1{2^n}\right)^2$$ where the sum is taken over all $2^{n-1}$ combinations of plus and minus signs? If the sum is too hard to get exactly, is it possible to find a good lower bound? I'm using this to calculate a Lebesgue integral.

For example, for $n=3$, the sum is $$\left(\dfrac12-\dfrac18+\dfrac14+\dfrac18\right)^2+\left(\dfrac12-\dfrac18+\dfrac14-\dfrac18\right)^2+\left(\dfrac12-\dfrac18-\dfrac14+\dfrac18\right)^2+\left(\dfrac12-\dfrac18-\dfrac14-\dfrac18\right)^2$$

• I'm confused on what the sum is. Would you mind writing the case $n=3$? – Daniel Montealegre Sep 19 '13 at 6:01
• @DanielMontealegre Done. – PJ Miller Sep 19 '13 at 6:04

Hint: $\sum (a_1 \pm a_2 \pm \ldots \pm a_n)^2 = 2^{n-1} \sum a_i ^2$.
To prove this, observe that the cross terms $a_i a_j$ will cancel out, and the coefficients of each $a_i ^2$ term are all 1.
Now apply this with $a_1 = \frac{1}{2} - \frac{1}{2^n}$ and $a_i = \frac{1}{2^i}$ for $i \geq 2$ to get the exact sum.