60
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ This addition of powers of two, and many other examples, are all geometric series. There's a lot of visualisations of this out there. $\endgroup$ Commented Oct 29, 2016 at 10:58
  • 3
    $\begingroup$ Write the numbers in base 2: The powers of $2$ starting from $1=2^0$ will be in binary, $1+10+100+1000$ will always be a number that will be a n with all binary digits 1. This is the largest number having that many digits. SO it is of the form $2^{n+1}-1$ $\endgroup$ Commented Oct 29, 2016 at 11:01
  • 1
    $\begingroup$ I think there's a counting/probabilistic way to approach this something about having $n$ binary choices $\endgroup$
    – BCLC
    Commented Oct 31, 2016 at 11:17

11 Answers 11

126
$\begingroup$

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

$\endgroup$
4
  • 8
    $\begingroup$ Very clever proof! $\endgroup$ Commented Nov 28, 2020 at 4:16
  • $\begingroup$ Amazing proof…loved it! πŸ‘ $\endgroup$
    – raza.sayed
    Commented Jun 27, 2021 at 20:54
  • $\begingroup$ Is there a rule that maps $m^n = \sum_{i \in K}2^i | K $is the set of exponents that would make the sum match $ ; m,n \in N$? $\endgroup$
    – juanmf
    Commented Jun 20, 2022 at 17:21
  • $\begingroup$ Asked a Q about my last comment $\endgroup$
    – juanmf
    Commented Jun 20, 2022 at 18:49
20
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Yes, but the OP said that he already knew this. What he is asking for is a visual representation of the proof. $\endgroup$
    – Alex M.
    Commented Oct 29, 2016 at 11:01
  • 7
    $\begingroup$ Actually, they said that they knew proof by induction, but didn't know how one would come up with the formula in the first place. At least that is how I understood the question. @AlexM. $\endgroup$
    – Ennar
    Commented Oct 29, 2016 at 11:02
12
$\begingroup$

There is a geometrical explanation.

Take a box long enough to put twice the amount of items equal to the last term of the sum, and try to pack it.

Let's take a box of length $2 * 2^n$.

Let's put the items from the first term ($2^n$) into the box. Now exactly one half of the space is left for the other terms, from $2^{n-1}$ down to $1$, so we repeat this process, starting from the next largest term.

As we put the items from each term, we notice that they take exactly one half of the empty space left in the box, because both the largest term left and the space left decreases in half on each step.

At some point we reach the first term, which is equal to 1, and there are two empty places left in the box for just one item, so after we put the last item into the box, there is still space for one more item.

The length of the box is $2*2^n = 2^{n+1}$, but it could be shorter by one, which is $2^{n+1} - 1$, and this is our formula.

For example, let's pack: $$\sum_{i=0}^3 2^i$$

Box length: $$2 * 2^3 = 16$$

2^3    |● ● ● ● ● ● ● ●|               |
2^2    |β—‹ β—‹ β—‹ β—‹ β—‹ β—‹ β—‹ β—‹|● ● ● ●|       |
2^1    |β—‹ β—‹ β—‹ β—‹ β—‹ β—‹ β—‹ β—‹|β—‹ β—‹ β—‹ β—‹|● ●|   |
2^0    |β—‹ β—‹ β—‹ β—‹ β—‹ β—‹ β—‹ β—‹|β—‹ β—‹ β—‹ β—‹|β—‹ β—‹|●| |

It could be shorter by one: $$2^{3+1}-1 = 15$$

By the way, similar geometrical explanation can be used for the ever decreasing geometric progression $\sum_{i=0}^\infty 2^{-i}$ with the only difference that we do not need to account for the last piece of empty space, because it tends to 0. Instead, we take some continuous medium as an example, such as a ribbon or a thread, which can be divided virtually infinitely so it sums to exactly a length of 2 units.

$\endgroup$
1
7
$\begingroup$

Another famous approach is to count the $2$-player games to determine a winner among $2^{n+1}$ people. It's $2^{n+1}-1$, the number of people to eliminate. It's also $2^n$ people eliminated in the first round, halving each round until we reach the final.

$\endgroup$
1
  • $\begingroup$ Very beautiful and efficient proof ! $\endgroup$
    – projetmbc
    Commented Oct 23, 2020 at 9:57
6
$\begingroup$

There is a combinatorial interpretation. Consider the collection of all binary sequences of length $n+1$ with at least one $1$ (call this set $E$). There are $$2^{n+1}-1$$ such sequences because only $0...0$ isn't. Now let $E_j$ be the set of binary sequences of length $n+1$ such that the first $1$ is in the $j$ th component for $j=1,\dotsc, n+1$. Then $|E_j|=2^{n+1-j}$. Then the $(E_j)$ partition $E$ and we have that $$ 1+2+2^2+\dotsb+2^n=\sum_{j=1}^{n+1}2^{n+1-j}=2^{n+1}-1. $$ Alternatively consider the telescoping sum: $$ \sum_{k=0}^n 2^{k}=\sum_{k=0}^n (2^{k+1}-2^k)=2^{n+1}-1. $$

$\endgroup$
6
$\begingroup$

Another pictorial proof, similar to the box packing reply, is to count the number of nodes in a complete binary tree with n+1 levels.

$$\sum_{i = 0}^{n} 2^i$$

is the number of nodes in the complete binary tree for the levels 0 (the root) through n.

If you draw an example and number the nodes like this

       1  
     /   \
    2     3
   / \   / \
  4   5 6   7 
 / \ 
8   ...

etc. you will notice that the left-most node of each level is a power of 2 (1, 2, 4, 8, 16, ...).

so the number of nodes in the tree from root to level n is 2^{n+1} - 1.

$$ \sum_{i = 0}^{n} 2^i = 2^{n+1} - 1 \,.$$

$\endgroup$
5
$\begingroup$

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

enter image description here

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.

$\endgroup$
1
$\begingroup$

Another geometric interpretation.

Start with a line segment, AB. Extend this into a line. Use compassto mark off a point C by setting center at B and passing radius through A. Then lengths, AB=BC. Create point D in a similar way. We have thus constructed a length double that of the original line segment.

This doubling can continue AS MUCH S you like.

Now ignore the first line segment, AB.

The series of segments now starts with BD which has double the length of AB.

In general the nth segment in the first case is the n-1th segment upon removal of AB. Further, each is double the length of its corresponding section.

So By subtracting a part we've doubled what remains, but with fewer sections to account for.

This gives the formula.

$\endgroup$
0
$\begingroup$

Not sure if my answer has been posted yet, but here's how I understand it.

You are trying to understand why

$2^{n+1} - 1 = 2^n + 2^{n-1} + 2^{n-2} . . . + 2^1 + 2^0$

Suppose we take 2^n in the sum. We know since these are powers of two, that the previous term will be half of 2^n, and the term before that a quarter of 2^n.

Let n in 2^n be 1, or 2^1 = 2. The term before in the sum will be half of 2, so we can also write the entire sum as:

$2^1 + \frac{1}{2}(2^1)$

If you do this but for different values of n for 2^n you will find you can rewrite the sums as:

$2^n + \frac{ 2^n - 1}{2^n} ( 2^n)$

You can simplify this because you're dividing (2^n) - 1 by 2^n, and then multiplying it by 2^n which cancel each other out. The new simplified version with the cancellation will look like:

$2^n + 2^n - 1$

This can also be written as: $2( 2^n) - 1$

Further simplified into: $2^{n + 1} - 1$

And that is why that formula shows up! Hope this helps ( I'm not sure if this was the mathematical induction proof you already knew, I'm young and discovered this on my own so I don't know what this is).

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Welcome to stackexchange. That said, this is an answer to a six year old question that has many good answers, some of which closely match yours. If you want to help here, look at new questions that need answers you can provide. But wait until the OP shows some work before you jump in. $\endgroup$ Commented Jul 21, 2022 at 23:28
  • $\begingroup$ Did you mean $2^{k+1}$ where you typed $2^k+1$? $\endgroup$ Commented Feb 21 at 3:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .