Time complexity of ArrayList Insertion : Calculating sum of X + X/2 + X/4 + X/8 + ... 1 Here is an excerpt from Cracking Coding Interview book where it's talking about the time complexity of insertion to an ArrayList.

I am trying to prove that the sum of $X + \frac{X}{2} + \frac{X}{4} + \frac{X}{8} + .... 1 $ is $2X$.
Given,
\begin{align}
 &amp; X + \frac{X}{2} + \frac{X}{4} + \frac{X}{8} + .... 1 \\
 &amp; = X (1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + .... \frac{1}{X}) \\ 
 &amp; = 2^n (\frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^n}) \\
&amp; = 2^n * S_{n+1}
\end{align}
Here, $S_{n+1}$ is the sum upto $n+1$ elements,
\begin{align}
 S_{n+1} &amp; =  \frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^{n-1}} + \frac{1}{2^n} \\
 S_{n+1} - \frac{1}{2^n} &amp; = \frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^{n-1}} \\
 S_{n+1} - \frac{1}{2^n} &amp; = S_n
\end{align}
Also,
\begin{align}
 S_{n+1} &amp; =  \frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^{n-1}} + \frac{1}{2^n} \\
 2S_{n+1} &amp; = 2 + \frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^{n-1}} \\
2S_{n+1} &amp; = 2 + S_n \\
2S_{n+1} -2 &amp; = S_n \\
\end{align}
Now combining both,
\begin{align}
 S_{n+1} - \frac{1}{2^n} &amp;= 2S_{n+1} -2 \\
S_{n+1} &amp;= 2 - \frac{1}{2^n}
\end{align}
As n approaches infinity, $S_{n+1} = 2$
This is as far as I've gotten. I am wondering how to continue from here. Also, am I in the right path?

15 minutes later here is what I've figured out.
Placing the value of $S_{n+1}$ back to the original expression,
\begin{align}
 &amp; X + \frac{X}{2} + \frac{X}{4} + \frac{X}{8} + .... 1 \\
 &amp; = X (1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + .... \frac{1}{X}) \\ 
 &amp; = 2^n (\frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^n}) \\
&amp; = 2^n * S_{n+1} \\
&amp; = 2^n (2 - \frac{1}{2^n})\\
&amp; = 2^n * 2 - 1\\
&amp; = 2X - 1\\
&amp; \approx 2X \\
\end{align}
But I am not sure if it's correct. I've appreciated some input.
Let's take main phrase from your book:
&quot;If you read this sum left to right, it starts with 1 and doubles until it gets to $X$&quot;
This means, that $X=2^k$, for some $k$. So, simply using geometrical progression, we have
$$1+2+4+\cdots+2^k=\frac{X}{2^k} +\frac{X}{2^{k-1}} + \cdots+\frac{X}{2^2}+\frac{X}{2}+ X = \frac{1-2^{k+1}}{1-2}=2^{k+1}-1=2X-1$$