CSC300 / CSC402: Adding up an geometric series [4/7] Previous pageContentsNext page

Suppose we add up the elements we get counting by multiplying 2: 

1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + ... + N

Let's count to 16! 

01 
02 02 
04 04 04 04 
08 08 08 08 08 08 08 08 
16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16

The last element is so large that all the prior elements can be placed on top without overlapping

This is like flat packing 

08 08 08 08 08 08 08 08 04 04 04 04 02 02 01 
16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16

The sum is approximately 2 times N.

1 + 2 + 4 + 8 + ... + 2^k = 2^(k+1) - 1

Previous pageContentsNext page