Sum of the Powers of $2$

Question

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.

Answer 1

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}

Answer 2

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

Answer 3

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$

Answer 4

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

Answer 5

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