-1
$\begingroup$

This question already has an answer here:

The title says it all, I guess. Why $$\sum_{i=0}^{w-1}{2^i} = 2^w - 1$$

$\endgroup$

marked as duplicate by JMoravitz, clathratus, cmk, John Omielan, StubbornAtom Sep 11 at 18:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Call the sum $S(w)$. Can you relate $S(w)$ to $2S(w)$ in some helpful way? $\endgroup$ – lulu Sep 11 at 17:46
  • 2
    $\begingroup$ Do you recognize how/why $999999+1 = 1000000$? If we were in binary instead, why $111111_2+1_2=1000000_2$? As for a proof, have you ever heard of a proof by induction? $\endgroup$ – JMoravitz Sep 11 at 17:47
  • $\begingroup$ What have you tried? Can you show it is true for some special value of w? Are you familiar with induction? $\endgroup$ – M_B Sep 11 at 17:47
  • $\begingroup$ Yea I know that I could prove it by induction but isn't there some algebraic reasoning for the formula? $\endgroup$ – That Guy Sep 11 at 17:50
1
$\begingroup$

Here's another way to look at it. $$\begin{align}S=1+&2+4+8+\cdots+2^n\\ 2S=\ \ &2+4+8+\cdots+2^n+2^{n+1}\end{align}$$ Subtract the first equation from the second to get $S=2^{n+1}-1$

$\endgroup$
0
$\begingroup$

Here is an intuitive way to see it:

Say you want to compute $$1+2+2^2+2^3+2^4\tag{1}$$ If you add $1$ to the sum $(1)$ you'll get: $$(1+1)+2+2^2+2^3+2^4\\=(2+2)+2^2+2^3+2^4\\=(2^2+2^2)+2^3+2^4\\=(2^3+2^3)+2^4\\=(2^4+2^4)\\=2^5$$

Since we added $1$, the sum is $1$ less, that is, $$2^5-1$$

$\endgroup$
0
$\begingroup$

Say we set $$s_n(x)=\sum_{k=0}^{n-1}x^k.$$ We see that $$s_{n+1}(x)=x^n+s_n(x).$$ But we also see that $$xs_n(x)=\sum_{k=0}^{n-1}x^{k+1}=\sum_{k=1}^{n}x^k=s_{n+1}(x)-1.$$ Hence we have $$xs_n(x)=s_n(x)+x^n-1,$$ which means that for $x\ne 1$, $$s_n(x)=\frac{x^n-1}{x-1}.$$ The sum in question is given by $$\sum_{i=0}^{w-1}2^i=s_{w}(2)=\frac{2^w-1}{2-1}=2^w-1.$$

$\endgroup$

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