I'm brushing up on stuff related to analysis of algorithms. And I have a question about this PDF I found. This is where I'm confused:Question 2: What if instead we decide to double the size of the array when we resize?Answer 2: This is much better. Now, in any sequence of n operations, the total cost for resizing is $1 + 2 + 4 + 8 +. . .+ 2^i$ for some $2^i <  n$ (if all operations are pushes then $2^i$ will be the largest power of $2$ less than $n$).  This sum is at most $2n1$.  Adding in the additional cost of $n$ for inserting/removing, we get a total cost $<3n$, and so our amortized cost per operation is $< 3$.How did we arrive at $2n-1$? I know that the sum of powers of $2$ is $2^{n-1}-2$, but does that matter at all here? I know that $2^{n-1} -2$ is very different from $2n-1$, but I'm not seeing how you can get $2n-1$ from the sum of $1 + 2 + \dots +2^i$  where $2^i$ is largest power of $2$ before $n$ item. If anyone can give concrete examples, that would be great because that's how I understand better. I know where the remaining $n$ comes from which makes this whole operation $3n$. 
Amortized analysis for doubling resizing array is ~3n
algorithm analysis;mathematical analysis;amortized analysis
Note that the statement involves two variables $i$ and $n$. The sum of powers of two equals the next power minus one: $\sum_{k=0}^i 2^k = 2^{i+1}-1$. It is mentioned that $2^i$ is the largest power less than $n$. That means $2^i < n \le 2^{i+1}$.  As $2^i < n$ we have that the sum $2\cdot 2^i -1$ is less than $2n-1$.I am a little confused as the text states at most rather than less than.