How to prove that $2^0 + 2^1 + 2^2 + 2^3 + \cdots + 2^n = 2^{n+1} - 1$ When I'm reading Computer Systems: A Programmer's Perspective, I met the sum of binary numbers and failed to prove it:
$$ 2^0 + 2^1 + 2^2 + 2^3 + \cdots + 2^n = 2^{n+1} - 1 $$
This might be preliminary knowledge, I'm not good at mathematics, any body could give me a hint?
 A: Express each power $2^k$ in binary: you get one bit 1 and the rest is 0. When you sum these up, you get a number with all bits 1. Adding one to this number yields a number with one bit 1, thus a power of 2. Here is an example with $n=6$: 
 0000001
 0000010
 0000100
 0001000
 0010000
 0100000
 1000000
--------
 1111111 = 10000000-1
       1
--------
10000000

A: Since $1= 2-1$, you can multiply by $2-1$ and it won't change the value.
$$(2-1)(2^0+2^1+2^2+\cdots + 2^n) $$
$$=2(2^0+2^1+2^2+\cdots + 2^n) -1(2^0+2^1+2^2+\cdots + 2^n)$$
$$= (2^1+2^2+2^3+\cdots + 2^{n+1}) - (2^0+2^1+2^2+\cdots +2^n)$$
$$= 2^{n+1}-2^0.$$
A: $$\begin{array}{rcll}
2S & = & &&2 &+& 2^2& + &2^3& +& \cdots &+& 2^{n}&+&2^{n+1}\\
-S & = & -1 & - &2 & - &2^2 &-& 2^3 & -&\cdots& - &2^n\\\hline
S & = & -1&+&&&&&&&&&&+&2^{n+1}
\end{array}$$
A: To compute the sum
$$
S = 1 + x + x^2 + \ldots + x^{N},
$$
first compute the expression $(1 - x) \: S$.  On expanding it and collecting like terms, you will see that
$$
(1 - x) \: S = 1 - x^{N+1}.
$$
In your case, $x = 2$, but this works for all $x \neq 1$.
A: This is a geometric series with common ratio 2.  A typical way to see how to sum is to call
$$ s = 1+x+x^2+\cdot + x^n$$
then
$$sx = x+x^2+x^3+\cdot +x^{n+1}$$
Subtracting we find
$$
\begin{align}
s-sx &= 1-x^{n+1} \\
s(1-x)&= 1-x^{n+1}\\
s& = \frac{1-x^{n+1}}{1-x}
\end{align}$$
A: Notice $2^0=2^1-1$.
Then $2^0+2^1=2(2^1)-1=2^2-1$
Then $2^0+2^1+2^2=2(2^2)-1=2^3-1$.
We have $2^0+2^1+2^2...2^{n-1}=2(2^{n-1})-1=2^n-1$.
And to show the this holds for the $n+1$ case, notice that $(2^n-1)+2^n=2(2^n)-1=2^{n+1}-1$.
A: Exploiting the binary representation,
$$111\cdots111_2+1_2=1000\cdots000_2$$ because the carry propagates.
This is exactly
$$2^0+2^1+2^2+\cdots2^{n-2}+2^{n-1}+2^n+1=2^{n+1}.$$

The proof generalizes to other bases. Let $a:=b-1$, then
$$a\cdot111\cdots111_b+1_b= aaa\cdots aaa_b+1_b=1000\cdots000_b,$$ which is a rewrite of
$$(b-1)(b^0+b^1+b^2+\cdots b^{n-2}+b^{n-1}+b^n)+1=b^{n+1}$$ or
$$b^0+b^1+b^2+\cdots b^{n-2}+b^{n-1}+b^n=\frac{b^{n+1}-1}{b-1}.$$
A: You are going to walk a distance of one mile. You walk half the distance and rest. You then walk half the remaining distance and rest. Continue doing this.
So now we can write down everyone's favorite infinite series,
$\frac{1}{2} +\frac{1}{4} +\frac{1}{8} +\frac{1}{16} + \dots  = 1$
Multiply both sides by by $2^{n+1}$,
$2^{n} + 2^{n-1} + 2^{n-2} +...+2^2+2^1+2^0+\frac{1}{2} +\frac{1}{4} +\frac{1}{8} +\dots = 2^{n+1}$.
OR
$2^{n} + 2^{n-1} + 2^{n-2} +...+2^2+2^1+2^0+1 = 2^{n+1}$.
Subtracting $1$ from each side,
$2^{n} + 2^{n-1} + 2^{n-2} +...+2^2+2^1+2^0 = 2^{n+1}-1$.
A: You can also do the following. Let S denote the following sum
$S=2^0+2^1+2^2+...+2^n$
Multiply both sides of the equation by 2 and you will obtain the following:
$2S=2^1+2^2+...+2^n+2^{n+1}$
Subtract the first equation from the second one to get:
$S=2^{n+1}-2^0=2^{n+1}-1$ which is the desired equation. I really hope this helps! 
