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}}}$ 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?
 A: $$\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}}}.$$
A: 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}}$$
A: 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.
