While reading the text Introduction to Algorithms by Cormen et. al. I came across a few mathematical step which I felt like proving in a more detailed manner, as I could not get steps of the mathematics which they did in short.
Below is the excerpt from the text.
$$c_i = \begin{cases} i &\quad\text{if $i-1$ is an exact power of $2$ }\\ 1&\quad\text{otherwise.}\\ \end{cases}$$
So,
$$\sum_{i=1}^{n}c_i\leq n+\sum_{j=0}^{\lfloor lg(n) \rfloor}2^j\tag 1$$ $$<n+2n=3n$$
The following is my attempt to understand the step $(1)$
$$\sum_{i=1}^{n}c_i=\sum_{\text{$i-1$ is a power of 2}}c_i +\sum_{\text{$i-1$ is not a power of 2}}c_i $$
$$=\sum_{\text{$j$ is a power of 2}}(j+1) +\sum_{\text{$j$ is not a power of 2}}(1) ,\quad\quad\text{where $j=i-1$}$$
$$=\sum_{\text{$j$ is a power of 2}}(j) +\sum_{\forall j}(1) = \left (\sum_{\text{$j$ is a power of 2}}j\right )+n \tag 2$$
$$\text{where $0\leq j \leq n-1$}$$
for the situation in which $j$ is power of $2$ let $2^k$ be the maximum possible value of $j$. So,
$$2^k=n-1 \implies k=\lfloor \log_2(n-1) \rfloor$$
Now we know,
$$n-1<n \implies \log_2(n-1)<\log_2(n) \implies \lfloor\log_2(n-1)\rfloor\leq\lfloor\log_2(n)\rfloor \tag3$$
Let $j=2^t$ , $t=0$ to $k$
So from $(2)$ and $(3)$ we have,
$$\sum_{i=1}^{n}c_i\leq n+\sum_{t=0}^{\lfloor lg(n) \rfloor}2^t \tag 4$$
The step which the authors achieved directly in $(1)$ took me so many steps to understand or derive in $(4)$. Is there a shorter method available or some intuition which the authors used to achieve the result directly?
If $i-1=2^j$, where $i\le n$ then $j=\lg(i-1)<\lg n$. Moreover, $j$ is an integer, so $j\le\lfloor\lg n\rfloor$. Thus, each term of $\sum_{i=1}^nc_i$ is either $1$ or $2^j+1$ for some $j$ such that $0\le j\le\lfloor\lg n\rfloor$. Thus, we automatically get a contribution of $1$ from each of the $n$ terms, for a total of $n$. We get another $2^j$ for the terms with $0\le j\le\lfloor\lg n\rfloor$, which contribute
$$\sum_{j=0}^{\lfloor\lg n\rfloor}2^j=2^{\lfloor\lg n\rfloor+1}-1<2\cdot2^{\lg n}=2n\;.$$
Thus,
$$\sum_{i=1}^nc_i\le n+\sum_{j=0}^{\lfloor\lg n\rfloor}2^j<n+2n=3n\;.$$