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}}}$

Question

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?

Answer 1

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

Answer 2

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}}$$

Answer 3

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.