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$$

  • $\begingroup$ I'm confused on what the sum is. Would you mind writing the case $n=3$? $\endgroup$ – Daniel Montealegre Sep 19 '13 at 6:01
  • $\begingroup$ @DanielMontealegre Done. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.