Why is it that $$2^{10} + 2^{9} + 2^{8} + \cdots + 2^{3} + 2^2 + 2^1 = 2^{11} - 2?$$
7 Answers
$\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}$
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
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$
-
$\begingroup$ This is correct; however, I excluded $2^0$ from my count. $\endgroup$– okarinJan 5, 2014 at 21:52
-
-
$$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$$
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.
-
$\begingroup$ General proof of the sum of any Geometric Sequence exactly is what @Zafer Cesur said. $\endgroup$– RShJan 5, 2014 at 21:58