Prove a summation equals 1

Question

I'm working on an algorithms problem and I've come to the following generalization, but I'm not sure how to prove it. Could anyone help?

$$ \sum_{i\ =\ 1}^{n-1}\frac{1}{2^{i}}\ +\ \frac{1}{2^{n-1}}\ =\ 1 $$

Answer 1

We have $$ \sum_{i=1}^{n-1}\frac{1}{2^{i}}+ \frac{1}{2^{n-1}}\\ =\frac12+\frac1{2^2}+\cdots+\frac1{2^{n-2}}+\frac1{2^{n-1}}+\frac1{2^{n-1}} $$ Now add the two rightmost terms together, and simplify them, and you get $$ =\frac12+\frac1{2^2}+\cdots+\frac1{2^{n-3}}+\frac1{2^{n-2}}+\frac1{2^{n-2}} $$ And then you can repeat this, adding the two rightmost terms and simplify, all the way until you reach $\frac12+\frac12=1$.

Answer 2

Hint: $\sum_{i=0}^{n-1}x^{i}=\frac{x^n-1}{x-1}$, can you take it from here?

Answer 3

Use mathematical induction:

• Base Case:

  • When $n=2$ we have $$\frac 1{2^{2-1}}+\sum\limits_{i=1}^{2-1}\frac 1{2^i}=1$$ which is true as $\tfrac 12+\tfrac 12=1$.

• Iterative Case:

  • Suppose for all $n\geq 2$, that $$\frac{1}{2^{n-1}}+\sum\limits_{i=1}^{n-1}\frac1{2^{i}}=1$$
  • Now you need to derive that $$\frac{1}{2^{n}}+\sum\limits_{i=1}^{n}\frac1{2^{i}}=1$$

Answer 4

Hint: $$\sum_{i\ =\ 1}^{n} u_1\cdot r^{i-1} = \frac{u_1\big(r^n-1\big)}{r-1}$$

Apply this to $$\sum_{i = 1}^{n-1} \frac{1}{2^i}$$

and see what you get.