# Why is it that $2^{10} + 2^{9} + 2^{8} + \cdots + 2^{3} + 2^2 + 2^1 = 2^{11} - 2$?

Why is it that $$2^{10} + 2^{9} + 2^{8} + \cdots + 2^{3} + 2^2 + 2^1 = 2^{11} - 2?$$

Try looking at the terms in binary:

  2^10   10000000000
2^9     1000000000
2^8      100000000
2^7       10000000
2^6        1000000
2^5         100000
2^4          10000
2^3           1000
2^2            100
+ 2^1             10
---------------------
=        11111111110

+   2             10
=       100000000000 = 2^11


$\begin{eqnarray}{\bf Hint} &&\ \ \underbrace{2^{11}} \\ \,&=&\ \ \overbrace{2^{10} + \underbrace{2^{10}}}\\ \,&=&\ \ 2^{10} + \overbrace{{2^9+\underbrace{2^9}}}\\ \,&=&\ \ 2^{10} + 2^9+\overbrace{2^8+\underbrace{2^8}}\\ \,&=&\ \ 2^{10} + 2^9+2^8+\overbrace{2^7+2^7}\\ \,&&\qquad\qquad\ \ \vdots\qquad\qquad\qquad\ddots \end{eqnarray}$
Alternatively we can write it in telescopic form

$\ \begin{eqnarray} \color{#c00}{2^{11}-2^k} = \underbrace{\phantom{2^11 - 2^10}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\color{#c00}{2^{11}}}&&\overbrace{{-2^{10}} +\underbrace{\phantom{2^10 - 2^9}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!2^{10}}^{=\, 0}&&\overbrace{-2^9 +\underbrace{\phantom{2^9 - 2^8}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!2^9}^{=\,0}&&\overbrace{-2^8 + 2^8}^{=\,0} \cdots \overbrace{-2^{k+2} + \underbrace{\phantom{2^{k+2} - 2^{k+1}}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!2^{k+2}}^{=\, 0}&&\overbrace{-2^{k+1}+\underbrace{\phantom{2^{k+1} - 2^{k}}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!2^{k+1}}^{=\,0}&&\color{#c00}{-2^k}\\ &&\!\!2^{10}\quad\, + &&\!\!2^9\quad\, + &&\!\!2^8\quad +\quad\ \cdots\qquad + &&\!\!\!\!2^{k+1}\quad\ \ + &&\!\!\!2^k \end{eqnarray}$

Let $S = 1+2^1+2^2+...+2^{10}$

Multiply by 2

$2S = 2^1+2^2+2^3+...+2^{11}$

Substract the former from the latter:

$S = 2^{11}-1$

$1+2^1+2^2+...+2^{10} = 2^{11}-1$

• This is correct; however, I excluded $2^0$ from my count. – okarin Jan 5 '14 at 21:52
• @okarin: so subtract 1 at the end? – Ben Millwood Jan 5 '14 at 23:59
• @BenMillwood Yes – okarin Jan 6 '14 at 0:49

$$2^{10} + 2^{9} + 2^{8} +2^7+2^6+2^5+2^4+ 2^{3} + 2^2 + 2^1 = 2^{11} - 2$$

Add $(2-2)$ to the left-hand side, obtaining:

\begin{align} 2^{10} + 2^{9} + 2^{8} + 2^7+2^6+2^5+2^4 + 2^{3} + 2^2 + 2^1 \color{green}{+ 2 - 2} & = 2^{11} -2 \\ 2^{10} + 2^{9} + 2^{8} + 2^7+2^6+2^5+2^4 + 2^{3} + 2^2 + \color{maroon}{2^1 + 2^1} - 2 & = 2^{11} -2 \end{align}

Since $2^1 + 2^1 = 2\cdot(2^1) = 2^2$, the left side simplifies to:

$$2^{10} + 2^{9} + 2^{8} +2^7+2^6+2^5+2^4+ 2^{3} + \color{maroon}{2^2 + 2^2} - 2 = 2^{11} - 2$$

Since $2^2 + 2^2 = 2\cdot(2^2) = 2^3$, the left side simplifies to:

$$2^{10} + 2^{9} + 2^{8} + 2^7+2^6+2^5 + 2^{4} + \color{maroon}{2^3 + 2^3} - 2 = 2^{11} - 2$$

Repeat this simplification several more times:

$$2^{10} + 2^{9} + 2^{8} + 2^7+2^6+2^5 + \color{maroon}{2^4 + 2^4} - 2 = 2^{11} - 2 \\ \\ \vdots \\\color{maroon}{2^{10} + 2^{10}} - 2 = 2^{11} - 2\\ \color{maroon}{2^{11}} - 2= 2^{11} - 2$$

• It's a very nice point of view! – RSh Jan 5 '14 at 22:13

Here's an alternative argument using the fact that a set of $n$ elements has $2^n$ subsets. Consider subsets $S$ of the set $\{0,1,2,\dots,9,10\}$. Since this set has 11 elements, it has $2^{11}$ subsets. Now ask, for each $n$ in the range $0\leq n\leq 10$, how many of these subsets $S$ have $n$ as their largest element. Well, any such $S$ consists of the element $n$ together with some subset $S'$ of $\{0,1,\dots,n-1\}$. So there are $2^n$ choices for $S'$. Thus, $n$ is the largest element of exactly $2^n$ subsets $S$ of $\{0,1,2,\dots,9,10\}$. Therefore, the sum $2^{10}+2^9+\dots+2^2+2^1$ counts all the subsets $S$ of $\{0,1,2,\dots,9,10\}$ whose largest element is 10 or 9 or $\dots$ or 2 or 1. That means it counts all of the $2^{11}$ subsets $S$ of $\{0,1,2,\dots,9,10\}$ except for two, namely the empty set and the set $\{0\}$. So the sum is $2^{11}-2$.

Try using the fact that $x^n + x^{n - 1} + \cdots + x + 1 = \frac{x^{n + 1} - 1}{x - 1}$.

Your sum is as follow: $2(2^9+2^8+\cdots +2+1)$ which can be proved simply is equal to $2 \frac{2^{10}-1}{2-1}$ as desired.

• General proof of the sum of any Geometric Sequence exactly is what @Zafer Cesur said. – RSh Jan 5 '14 at 21:58