There is an exercise (17.1-3) in the book CLRS that is as follows:
Suppose we perform a sequence of n operations on a data structure in which the i'th operation costs i if i is an exact power of 2, and 1 otherwise. Use aggregate analysis to determine the amortized cost per operation.
Now while i know this is CS related it is the rewriting of a summation in the suggested answer i am unsure about. A suggested answer is the following:
Let $n$ be arbitrary, and have the cost of operation $i$ be $c(i) .$ Then we have, $$ \begin{aligned} \sum_{i=1}^{n} c(i) &=\sum_{i=1}^{\lceil lg n\rceil} 2^{i}+\sum_{i \leq n \text { is not a power of } 2} 1 \\ & \leq \sum_{i=1}^{\lceil lg n\rceil} 2^{i}+n \\ &=2^{1+\lceil lg n\rceil}-1+n \\ & \leq 2 n-1+n \\ & \leq 3 n \in O(n) \end{aligned} $$ To find the average, we divide by $n,$ and the amortized cost per operation is $O(1) .$
So my question is - why/how do they rewrite the sum in line 1?
This is a slight variation of your stuff: $$\sum_{i=1}^{n} c(i) = \sum_{1\leq i \leq n, \text { $i$ is a power of } 2} i +\sum_{1\leq i \leq n, \text { $i$ is not a power of } 2} 1 \leq 2n-1+n \in O(n)$$ because $$ \sum_{1\leq i \leq n, \text { $i$ is a power of } 2} i = \sum_{1\leq 2^k \leq n} 2^{k}= \sum_{0\leq k \leq \log_2(n)} 2^{k} \leq 2^{1+\log_2(n)}-1 =2 n-1$$ and $$\sum_{1\leq i \leq n, \text { $i$ is not a power of } 2} 1\leq \sum_{i=1}^n 1=n.$$ Is it clear now?