# Prove a summation equals 1

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

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

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

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

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.