Let $F(z)=\sum_{n\geq 0}\frac{z^n}{2^n-1}$. Then $F(2z)-F(z)=
\frac{1}{1-z}$. Assume that $F(z)$ is rational. Thus $F(z)$ has a  
pole at some $z_0\neq 0$, and$F(2z)$ has a pole at $z_0/2$. Let $z_1$ be
a pole of $F(z)$ of maximum absolute value. Let $z_2$ be a pole of
$F(2z)$ of minimum absolute value. Then $z_2\neq z_1$, and both $z_1$
and $z_2$ are poles of $F(2z)-F(z)$, a contradiction.

The "standard" necessary and sufficient condition for a power series
$\sum a_n z^n$ to be a rational function is that the infinite Hankel
matrix $[a_{i+j}]_{i,j\geq 0}$ has finite rank, but I don't know if this
can be applied to the present question. See *Enumerative
Combinatorics*, vol. 1, 2nd ed., Exercise 4.6.