2
$\begingroup$

Possible Duplicate:
Summation equation for $2^{x-1}$

I'm solving the classic problem of the inventor of chess, who according to legend sold the invention for one grain for the first square of the board, 2 for the second, 4 for the third, 8 for the fourth, and so on. The question is what this amounts to, with the board having 64 squares.

$\sum_{k=0}^{63}2^{k} = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^{62} + 2^{63}$

$= \frac{2^0(2^{63+1} + 1)}{2 - 1} = 2^{64} + 1$

This answer seems reasonable, but according to the text book it should be $2^{64} - 1$. Why? Where am I going wrong?

  • 0
    Discovered my mistake - it was supposed to be $2^{64} - 1$, not $2^{64} + 1$.2012-08-30

4 Answers 4

10

Just for a bit of variety, you might like to evaluate the sum as follows. If $S = 2^0 + 2^1 + \dots + 2^{63},$ then, multiplying by 2, you get $2S = 2^1 + 2^2 + \dots + 2^{64},$ and then subtracting the first from the second you get: $S = 2^{64}-2^0 = 2^{64} - 1.$

6

Just imagine the result in binary it will have 64 binary digits (one per square) : $1_{(2)}+10_{(2)}+100_{(2)}+\cdots=1111\cdots 1111_{(2)}=2^{64}-1$

  • 1
    +1 for interesting way to think of this that is not in a calculus book (as the other answers are), and yet it is simpler than what is.2012-08-30
5

To add to Raymods answer.

An $n$-bit number with binary expansion of all $1$'s is equal to $2^{n} - 1$. To see why: $ \underbrace{11 \cdots 1}_{n\text{ times}} = \color{red}{1\ \underbrace{00\cdots 0}_{n\text{ times}}} - 1 = \color{red}{2^n} - 1.$ Because we know that a $1$ shifted to the left $n$ bits is equal to $2^n$.

4

The formula for Geometric Series is

$S_n = a + ar +ar^2 + ... + ar^{n -1} = a \left( {r^n - 1 \over r - 1}\right)$