Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

4 Answers 4

up vote 10 down vote accepted

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

share|improve this answer

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

share|improve this answer
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

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

share|improve this answer

The formula for Geometric Series is

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

share|improve this answer

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