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} & X + frac{X}{2} + frac{X}{4} + frac{X}{8} + …. 1 \ & = X (1 + frac{1}{2} + frac{1}{4} + frac{1}{8} + …. frac{1}{X}) \ & = 2^n (frac{1}{2^0} + frac{1}{2^1} + frac{1}{2^2} + frac{1}{2^3} + …. frac{1}{2^n}) \ & = 2^n * S_{n+1} end{align}

Here, $$S_{n+1}$$ is the sum upto $$n+1$$ elements,

begin{align} S_{n+1} & = 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} & = 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} & = S_n end{align}

Also,
begin{align} S_{n+1} & = 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} & = 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} & = 2 + S_n \ 2S_{n+1} -2 & = S_n \ end{align}

Now combining both,
begin{align} S_{n+1} – frac{1}{2^n} &= 2S_{n+1} -2 \ S_{n+1} &= 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} & X + frac{X}{2} + frac{X}{4} + frac{X}{8} + …. 1 \ & = X (1 + frac{1}{2} + frac{1}{4} + frac{1}{8} + …. frac{1}{X}) \ & = 2^n (frac{1}{2^0} + frac{1}{2^1} + frac{1}{2^2} + frac{1}{2^3} + …. frac{1}{2^n}) \ & = 2^n * S_{n+1} \ & = 2^n (2 – frac{1}{2^n})\ & = 2^n * 2 – 1\ & = 2X – 1\ & approx 2X \ end{align}

But I am not sure if it’s correct. I’ve appreciated some input.