Doubling Pennies
Which is more: being given one million dollars, or one penny the first day, double that penny the next day, then double the previous day's pennies and so on for a month?

It certainly looks as if a million dollars is more than all those pennies added up, because each penny is worth so little. How could even a whole lot of pennies be anywhere near a million dollars?

To begin, let's look at what happens in the first five days and see if we can find a pattern.
```       Day    No.of Pennies Given    Total No.of Pennies

1                 1                         1
2        1 x 2 =  2                  1+2 =  3
3        2 x 2 =  4                1+2+4 =  7
4        4 x 2 =  8              1+2+4+8 = 15
5        8 x 2 = 16           1+2+4+8+16 = 31

```
We see that the series whose sum gives the total number of pennies follows a regular pattern: each new term added to it is a power of two. This is an example of a geometric series. A geometric series is defined as having a constant ratio between consecutive terms.

In our case, we are told that the number of pennies given each day is double the number given the day before, which suggests that the ratio of this series is 2. Let's check:

```     no. pennies given on second day      2
-------------------------------  =  ---  =  2
no. pennies given on first day       1

no. pennies given on third day       4
-------------------------------  =  ---  =  2
no. pennies given on second day      2

no. pennies given on fourth day      8
-------------------------------  =  ---  =  2
no. pennies given on third day       4

```
Indeed, the ratio of the geometric series that gives the total number of pennies on a particular day is 2.

Having found this ratio, we can now use the fact that the sum of a geometric series (called S) with n terms whose ratio is r is the following:

S = (first term)(1-r^n)/(1-r)

This means that for our penny series with a first term of 1 and a ratio of 2, we find the sum after n days

= 1(1 - 2^n) / (1 - 2)
= - (1 - 2^n)
= 2^n - 1

We can also arrive at this formula by looking at the number of pennies we'll have after a given number of days. The number of pennies we will have is always one less than a power of two. For instance:
```       Day           Number of Pennies

1            2^1-1 =  2-1 =  1
2            2^2-1 =  4-1 =  3
3            2^3-1 =  8-1 =  7
4            2^4-1 = 16-1 = 15

```
We see that on day n we will have 2^n - 1 pennies - the same formula we arrived at above by using the fact that our series is geometric.

Now for our problem. Using our formula, since a month has about 30 days we will let n equal 30. This means that after a month we will have 2^30 - 1 pennies. Is this more than a million dollars?

Well, 2^30 - 1 = 1,073,741,824 - 1 = 1,073,741,823 pennies. That's more than a billion pennies!

If we divide this number by 100 (remember, there are 100 pennies in a dollar), we can find how many dollars this is:

1,073,741,823 divided by 100 = \$10,737,418.23. That's almost eleven million dollars!

If you keep doubling your pennies, you'll wind up with many more than a million dollars.

A similar problem involves a subject who does a favor for his queen. The queen asks how she can reward her subject; she is asked to place one grain of rice on the first square of a chessboard, two grains of rice on the second square, and so on for all the squares. How much rice will the subject receive?

This question is like our penny problem, only on a larger scale. There are 8 x 8 = 64 squares on a chessboard, so here we have the equivalent of doubling pennies for 64 days instead of 30. The subject receives 2^64 - 1 = 18,446,744,073,709,551,615 grains of rice.

These examples show that doubling a number, doubling that new number, and continuing on in this way quickly results in very large numbers. Adding all those large numbers up produces an even bigger number. So if your parents ever offer you an allowance of a penny on the first of the month, two pennies on the second, four pennies on the third, and so on, you should definitely take them up on it!