5
$\begingroup$

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

$\endgroup$

7 Answers 7

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$
0
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$
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$
3
  • $\begingroup$ This is correct; however, I excluded $2^0$ from my count. $\endgroup$
    – okarin
    Jan 5, 2014 at 21:52
  • $\begingroup$ @okarin: so subtract 1 at the end? $\endgroup$ Jan 5, 2014 at 23:59
  • $\begingroup$ @BenMillwood Yes $\endgroup$
    – okarin
    Jan 6, 2014 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$
1
  • $\begingroup$ It's a very nice point of view! $\endgroup$
    – RSh
    Jan 5, 2014 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$
1
  • $\begingroup$ General proof of the sum of any Geometric Sequence exactly is what @Zafer Cesur said. $\endgroup$
    – RSh
    Jan 5, 2014 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.