# Calculating the chess problem, sum $\sum_{k=0}^{63}2^{k}$ [duplicate]

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?

-

## marked as duplicate by Dilip Sarwate, Jennifer Dylan, N. S., Sasha, sdcvvcAug 31 '12 at 4:13

Discovered my mistake - it was supposed to be $2^{64} - 1$, not $2^{64} + 1$. –  Quispiam Aug 30 '12 at 16:03

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

-

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 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. –  Graphth Aug 30 '12 at 17:56

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$.
$$S_n = a + ar +ar^2 + ... + ar^{n -1} = a \left( {r^n - 1 \over r - 1}\right)$$