title: Aggregate analysis for a sequence of n operations
body: <p>I'm trying to find the amortized cost per operation in a sequence of <code>n</code> operations on a data structure in which the <code>ith</code> operation costs <code>i</code> if <code>i</code> is an exact power of 2, and 1 otherwise. </p>
  
  <p>I think I need to find a way to express the sum of the costs up to a number <code>n</code>, but I'm stuck. I can see that the special, more expensive <code>i</code> values are occurring father and farther apart:</p>
  
  <blockquote>
    <p>i = <strong>1 2</strong> 3 <strong>4</strong> 5 6 7 <strong>8</strong> 9 10 11 12 13 14 15 <strong>16</strong> 17 18 19 20... </p>
  </blockquote>
  
  <p>So, it looks like I have no numbers between the first and second powers of 2, then one number, then 3, then 7.  When I looked at this a while, I (correct me if this is off) found that the number of non-powers of 2 between the <code>jth</code> and <code>kth</code> powers of 2 is <code>2^(j-1) - 1</code>. </p>
  
  <p>But how can I tie this all together into a summation? I can kind of see something over the <code>js</code> combined with the number of actual powers of 2 themselves, but I'm having trouble uniting it all into a single concept. </p>