The idea behind the sum of powers of 2

Question

I know that the sum of powers of $2$ is $2^{n+1}-1$, and I know the mathematical induction proof. But does anyone know how $2^{n+1}-1$ comes up in the first place.

For example, sum of n numbers is $\frac{n(n+1)}{2}$. The idea is that we replicate the set and put it in a rectangle, hence we can do the trick. What is the logic behind the sum of powers of $2$ formula?

Answer 1

The binary expansion of $\sum_{k=0}^n2^k$ is a string of $n+1$ 1's: $$\underbrace{111\dots111}_{n+1}$$ If I add a 1 to this number, what do I get? $$1\underbrace{000\dots000}_{n+1}$$ 1 followed by $n+1$ 0's, hence $2^{n+1}$. Therefore $$\sum_{k=0}^n2^k=2^{n+1}-1$$

Answer 2

This works for any partial sum of geometric series.

Let $S = 1 + x + x^2+\ldots +x^n$. Then $xS = x + x^2 + \ldots +x^n + x^{n+1} = S - 1 + x^{n+1}$.

All you have to do now is solve for $S$ (assuming $x\neq 1$).

Answer 3

There is a combinatorial argument for why $$ 1 + q + q^2 + \dotsb + q^n = \frac{q^{n+1} - 1}{q - 1} $$ holds for any positive integer $q \neq 1$.

Consider the function $\gamma$ which takes a list $a = (a_1,a_2,\dotsc,a_{n+1})$ of length $(n+1)$ with components in $A = \{1,2, \dotsc, q\}$ and "compresses" it by cutting off repeating elements at the end of the list. For example, if $n = 3$ and $q = 7$,

\begin{align*} &\gamma(4,1,6,6) = (4, 1, 6),\\ &\gamma(2,2,3,7) = (2,2,3,7),\\ &\gamma(5,5,5,5) = 5,\\ &\gamma(7,4,4,4) = (7,4). \end{align*} More precisely, $\gamma$ is defined as $$ \gamma\colon \begin{cases} A^{n+1} \to A \cup B,\\ a \mapsto (a_1,a_2,\dotsc,a_{i(a)}) \end{cases} $$ where $$ B = \bigl\{\, a \in A^k : 2 \leq k \leq n+1 \text{ and } a_{k-1} \neq a_k \,\bigr\} $$ and $$ i(a) = \begin{cases} n+1 &\text{if } a_n \neq a_{n+1},\\ \min \{\, j : a_j = a_{j+1} = \dotsb = a_{n+1}\,\} &\text{else.} \end{cases} $$

Because $\gamma$ is a bijection, $A^{n+1}$ and $A \cup B$ have the same number of elements. $A^{n+1}$ has $q^{n+1}$ elements and the number of elements in $A \cup B$ equals the number of elements in $A$ plus the number of elements in $B$ (since $A$ and $B$ are disjoint). The number of elements in $B$ is $$ q(q-1) + q^2(q-1) + \dotsb + q^n(q-1), $$ since $q^k(q-1)$ is the number of lists of length $(k+1)$, whose last two elements are distinct. Putting the pieces together, we get $$ q^{n+1} = q + (q-1)(q + q^2 + \dotsb + q^n), $$ which is equivalent to the formula in question.

Answer 4

Here's a geometric intuition for why $2^0 + 2^1 + 2^2 + \dots + 2^n = 2^{n+1} - 1$:

Here's the idea. Notice that the boxes for $1 + 2 + 4$ are right next to a single box of size $8$. They perfectly fill that box once you add the gold square in, so $1 + (1 + 2 + 4) = 8$, meaning $1 + 2 + 4 = 8 - 1$. Similarly, the boxes for $1 + 2 + 4 + 8 + 16 + 32$ are right above a single box of size $64$, and the smaller boxes, plus the gold box, completely fill the box for $64$. That means that $1 + (1 + 2 + 4 + 8 + 16 + 32) = 64$, or that $1 + 2 + 4 + 8 + 16 + 32 = 64 - 1$.

More generally, this gives an intuition for why $1 + (2^0 + 2^1 + \dots + 2^n) = 2^{n+1}$: the boxes for the smaller powers of two, plus one gold box, perfectly fill the next box.

Answer 5

$(2^0 + 2^1 + 2^2 + \dots 2^k) = S$

Now multiply $S$ by $(2^1 - 2^0) = 1$

The middle terms cancel, leaving you with $2^k+1 - 1$.