5
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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
$\endgroup$
16
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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$

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

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.