# Can someone help me finish this: evaluate $S_n = \frac{x}{1-x^2}+\frac{x^2}{1-x^4}+ ... + \frac{x^{2^{n-1}}}{1-x^{2^{n}}}$ [duplicate]

I am asked to find the closed form solution for the below.

$$S_n = \frac{x}{1-x^2}+\frac{x^2}{1-x^4}+ ... + \frac{x^{2^{n-1}}}{1-x^{2^{n}}}$$

Just writing out the $$S_1, S_2, S_3$$, I have managed to find a pattern, which is:

$$S_n = \frac{S_{n-1}}{1-x^{2^n}} + \frac{x^{2^n}}{1-x^{2^{n+1}}}$$

I am not sure how to proceed onwards to solve this recurrence relation. Is there a clever trick I can do to solve it?

## 3 Answers

\begin{align} \frac{x}{1-x}-S_n &= \\ &= \frac{x}{1-x}-\frac{x}{1-x^2}-\frac{x^2}{1-x^4}- \ldots - \frac{x^{2^{n-1}}}{1-x^{2^{n}}} \\ &=\frac{x^2}{1-x^2}-\frac{x^2}{1-x^4}- \ldots - \frac{x^{2^{n-1}}}{1-x^{2^{n}}} \\ &=\ldots \\ &=\frac{x^{2^{n-1}}}{1-x^{2^{n-1}}}- \frac{x^{2^{n-1}}}{1-x^{2^{n}}} \\ &=\frac{x^{2^{n}}}{1-x^{2^{n}}}. \end{align}

So, $$S_n= \frac{x}{1-x}-\frac{x^{2^{n}}}{1-x^{2^{n}}}.$$

• ahh telescoping, I did it a bit differently and gave up on it. Nice spot
– Naz
Oct 6, 2018 at 14:56

Recognize the geometric series and replace it:

$$\frac{x}{1-x^2}=x+x^3+x^5+x^7+\cdots$$ For all the rest, it's the same, just replace $$x\to x^2,x^4,\ldots x^{2^n}$$.

Now notice that the new terms are just filling in the missing terms:

$$S_2=x+x^2+x^3+\Box+x^5+x^6+x^7+\Box+x^9+\cdots$$ $$S_3=x+x^2+x^3+x^4+x^5+x^6+x^7+\Box+x^9+\cdots+x^{15}+\Box+x^{17}\cdots$$

From this, it's easy to see that the limit of this sequence is just the full geometric series without missing terms: $$S_{\infty}=\frac{x}{1-x}$$. If you stop at term $$S_n$$, you are missing all powers of $$x^{2^n}$$ (for example, $$S_3$$ is missing $$x^8$$, $$x^{16}$$ and so on), and the missing terms are simply the geometric series with $$x^8$$ ($$x^{2^n}$$ in general) instead of $$x$$. This makes it easy to write like this:

$$S_{n}=S_{\infty}(x)-S_{\infty}(x^{2^n})=\frac{x}{1-x}-\frac{x^{2^n}}{1-x^{2^n}}$$

Just a kind of summary.

We have
\begin{align*} S_n&=\sum_{j=1}^n\frac{x^{2^{j-1}}}{1-x^{2^{j}}}\\ &=\sum_{j=1}^n\left(\frac{x^{2^{j-1}}}{1-x^{2^{j-1}}}-\frac{x^{2^j}}{1-x^{2^j}}\right)\tag{1}\\ &\,\,\color{blue}{=\frac{x}{1-x}-\frac{x^{2^{n}}}{1-x^{2^{n}}}}\tag{2} \end{align*}

Comment:

• In (1) we use the identity $$a^2-b^2=(a-b)(a+b)$$ with $$a=1$$ and $$b=x^{2^{j-1}}$$.

• In (2) we apply the telescoping series.