0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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$$
| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.