Sum of the Powers of $2$ Suppose I have a sequence consisting of the first, say, $8$ consecutive powers of $2$ also including $1$: $1,2,4,8,16,32,64,128$. Why is it that for example, $1 + 2 + 4 = 7$ is $1$ less than the next term in the series, $8$? Even if one was to try, for instance, $524,288 + 1,048,576$ ($2^{19}$ and $2^{20}$), the next term ($2^{21}$) will be $2,097,152$, which is one greater than the previous sum. I found this whilst solving the "if you are given a penny each day and it doubles" problem. Can someone please explain this to me? Thank you.
 A: This is because of the formula for the geometric series:
$$1+2+2^2+\dots +2^{19}+2^{20}=\frac{2^{21}-1}{2-1}=2^{21}-1.$$
A: This is a consequence of a well-known formula, but here is an elementary proof for your case, just using distributivity and the fact that $2 - 1 = 1$:
\begin{align}
(1 + 2 + 4 + \dots + 2^n) &= (2-1)(1 + 2 + 4 + \dots + 2^n) \\
&= 2(1 + 2 + 4 + \dots + 2^n) - (1 + 2 + 4 + \dots + 2^n) \\
&= (2 + 4 + 8 + \dots + 2^{n+1}) -  (1 + 2 + 4 + \dots + 2^n) \\
&= 2^{n+1} - 1
\end{align}
A: It's possible to prove that recursively. Suppose that $\sum_{k=0}^{n-1} 2^k=2^n-1$. Then we have:
$\sum_{k=0}^n 2^k= 2^n + \sum_{k=0}^{n-1} 2^k=2^n+2^n -1= 2\times 2^n -1= 2^{n+1}-1$
The base case ($n=0$) holds since $2^0=1=2^1-1$
A: If you think about the list of the positive integers written in base 2, it goes like this:
$$\begin{align*}
1&=1\cdot 2^0 &=1_2\\
2&=1\cdot 2^1 + 0\cdot 2^0 &=\textbf{10}_2\\
3&=1\cdot 2^1+1\cdot 2^0 &=11_2\\
4&=1\cdot 2^2+0\cdot 2^1+0\cdot 2^0 &=\textbf{100}_2\\
5&=1\cdot 2^2+0\cdot 2^1+1\cdot 2^0 &=101_2\\
6&=1\cdot 2^2+1\cdot 2^1+0\cdot 2^0 &=110_2\\
7&=1\cdot 2^2+1\cdot 2^1+1\cdot 2^0 &=111_2\\
8&=1\cdot 2^3+0\cdot 2^2+0\cdot 2^1+0\cdot 2^0 &=\textbf{1000}_2\\
9&=1\cdot 2^3+0\cdot 2^2+0\cdot 2^1+1\cdot 2^0 &=1001_2\\
\vdots&=\vdots &\vdots\\
2^{n}-1&=1\cdot2^{n-1}+1\cdot 2^{n-2}+\cdots + 1\cdot 2^0 &=111\ldots 1_2\\
2^n&=1\cdot 2^n + 0\cdot 2^{n-1} + \cdots + 0\cdot 2^0 &=\textbf{100}\ldots\textbf{00}_2
\end{align*}$$
The number of digits in the expression in base 2 changes exactly at the powers of 2, and right before changing the number (in base 2) looks like a sequence of 1's, which corresponds to the sum $2^0+\ldots+2^{n-1}$ for some $n$. 
Note that a similar idea will work for any base $b$.
A: Let $S = 1+2+4+...+2^n$.  Then $2S = 2+4+8+...+2^{n+1}$.  Take the difference between these equalities.  On the left side you get back $S$, on the right side most of the powers of 2 cancel out and what's left is $2^{n+1}-1$.
