<s>[INST] Need to prove formula for $\sum_{k=0}^{\infty} \frac{2^{k} z^{2^k}}{1 + z^{2^k}}$ I need help showing that for $|z|<1$ we have 
$\sum_{k=0}^{\infty} \frac{2^{k} z^{2^k}}{1 + z^{2^k}}$ = $\frac{z}{1-z}$
I tried using $\sum_{n=0}^{\infty} (-z^{2^k})^{n} = \frac{1}{1+z^{2^k}}$ but that hasn't gotten me very far. Any help is appreciated! 
 [/INST] Let 
$$\sum_{k=0}^{\infty} \frac{2^{k} z^{2^k}}{1 + z^{2^k}} =  \sum_{k=0}^{\infty} a_n z^n$$
and examine contributions to the $a_n$ from the various terms in the $k$ sum.
For $n=0$ none of the terms in the sum contributes (the $k=0$ contribution is 
$z-z^2+z^3-z^4+\ldots$).
For $n$ odd only the $k=0$ term contributes, and thus for $n$ odd, $a_n = 1$.
The $k=1$ term of the sum contributes to $(-1)^{n/2+1}2^1$ to each $a_n$ for $n$ even.  Higher $k$ terms give no contribution to $a_2$, or indeed to any 
$a_{4p+2}$, thus for $p\in\Bbb Z$
$$
a_{4p+2} = (-1) + 2 = 1 $$
The contributions of the $k=1$ term of the sum to each $a_{4p}$ is $-2$.
The $k=2$ term of the sum contributes to $(-1)^{n/4+1}2^2$ to each $a_n$ for $n$ divisible by $4$.  Higher $k$ terms give no contribution to  any 
$a_{8p+4}$, thus for $p\in\Bbb Z$
$$
a_{8p+4} = (-1) + (-2) + 4 = 1 $$
The contributions of the $k=2$ term of the sum to each $a_{8p}$ is $-4$.
The $k=3$ term of the sum contributes to $(-1)^{n/8+1}2^3$ to each $a_n$ for $n$ divisible by $8$.  Higher $k$ terms give no contribution to  any 
$a_{16p+8}$, thus for $p\in\Bbb Z$
$$
a_{16p+8} = (-1) + (-2) + (-4) + 8 = 1 $$
The contributions of the $k=2$ term of the sum to each $a_{8p}$ is $-8$.
Without going to the effort to formally introduce induction here, we can see the pattern:  For any even $n>0$, the net contributions always add to $1$, and for odd $n$ we already saw a value of $a_n = 1$.  Thus the result
is
$$
\sum_{k=1}^\infty z^n = \frac{z}{1-z}
$$
</s>