<s>[INST] 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?
 [/INST] 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}}$$
</s>