Is $$\sum_{n=1}^{\infty} \frac{z^n}{2^n-1} \in \mathbb{C}(z)\ ?$$
In a slightly different vein, given a sequence of real numbers $\{a_n\}_{n=0}^\infty$, what are some necessary and sufficient conditions for $\sum a_nz^n$ to be in $\mathbb{C}(z)$ with all poles simple?
The function $$ f(z)=\sum_{n=1}^{\infty} \frac{z^n}{2^n-1} $$ defines a holomorphic function for $|z|<2$, and it satisfies $$ f(2z) = f(z)+\frac{z}{1-z} $$ for $|z|<1$. Based on this identity, it is easy to prove that $f(z)$ extends to a meromorphic function on $\mathbb{C}$, and the set of poles is $\{2^n:\ n=1,2,\dots\}$. In particular, $f(z)$ does not define a rational function, because its meromorphic extension to $\mathbb{C}$ has infinitely many poles.
Regarding your second question, I recommend the work of Dwork (with which I am not familiar), e.g. (8) in Alain Robert's article "Des adèles: pourquoi", and Lemma 9 in Tao's blog. See also Remark 2 below.
Remark 1. A more direct proof of the above claims follows from the identity $$ \sum_{m=1}^\infty\frac{z}{2^m-z} = \sum_{n=1}^\infty \frac{z^n}{2^n-1},\qquad |z|<2. $$ Indeed, left hand side defines a meromorphic function on $\mathbb{C}$ with pole set $\{2^m:\ m=1,2,\dots\}$.
Remark 2. One can give a different, number theoretic proof using Eisenstein's theorem on algebraic functions (the proof was published by Heine because of Eisenstein's early death). Indeed, the Taylor coefficients of $f(z)$ around the origin are rational, but their denominators $2^n-1$ are not supported on finitely many primes by Fermat's little theorem. (As Gerald Edgar remarked below, this argument proves that $f(z)$ is not even algebraic.)
Let $F(z)=\sum_{n\geq 1}\frac{z^n}{2^n-1}$. Then $F(2z)-F(z)=
\frac{z}{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.
$\sum a_n z^n$ is a rational function iff $a_n$ is a sum of polynomials times exponentials. This is a straightforward corollary of partial fraction decomposition. So, suppose $\frac{1}{2^n - 1}$ can be expressed as such a sum. Taking $n \to \infty$ shows that the largest $r$, in absolute value, such that $r^n$ appears in this sum is $r = \frac{1}{2}$, and moreover (after multiplying both sides by $2^n$) that its polynomial coefficient must be the constant polynomial $1$. That is, the sum must begin
$$\frac{1}{2^n - 1} = \frac{1}{2^n} + \text{smaller terms}.$$
The next largest $r$ such that $r^n$ can apppear in this sum is determined by the asymptotic behavior of $\frac{1}{2^n - 1} - \frac{1}{2^n} = \frac{1}{2^n(2^n - 1)} \approx \frac{1}{4^n}$, and the same $n \to \infty$ and multiplying by $4^n$ argument as above shows that it must be $r = \frac{1}{4}$ with polynomial coefficient $1$. So the sum must continue
$$\frac{1}{2^n - 1} = \frac{1}{2^n} + \frac{1}{4^n} + \text{smaller terms}.$$
But it's clear that in fact we have
$$\frac{1}{2^n - 1} = \sum_{k \ge 1} \frac{1}{2^{kn}}$$
so this argument never terminates, and it follows that $\frac{1}{2^n - 1}$ cannot be expressed as a finite sum of polynomials times exponentials. This is a less complex-analytic version of the argument that proceeds by showing that the generating function has infinitely many poles.
I would not argue with the irrationality of the function following from the functional equation relating $f(2z)$ to $f(z)$. In fact this function is a particular case of the so-called $q$-logarithm which received a quite special attention. Note that being rational over $\mathbb C(z)$ or over $\mathbb Q(z)$ for a power series with rational coefficients is equivalent.
If $f(z)$ where rational then $$f(1)=\sum_{n=1}^\infty \frac1{2^n-1}=\sum_{m=1}^\infty \tau(m)2^{-m}$$ would be a rational number, where $\tau(m)$ denotes the number of divisors of $m$. Erdős proved already in 1948 that this is not the case by showing that the base $2$ expansion of the number is not periodic. (This is still a nice exercise in analytic number theory!)
The irrationality of the values of $f(z)$ for rational $z\ne0$ was established by P. Borwein in 1992 using the Padé approximations to the function.
Write $f_0(z)=\sum\frac{z^n}{2^n-1}$ and inductively define $f_k(z)=f_{k-1}(z)-\frac{1}{1-z/2^k}$. By induction, it is easy to see that $f_k$ is given by the power series $$f_k(z)=\sum\frac{z^n}{2^{kn}-2^{(k-1)n}}.$$
Since each $f_k$ has radius of convergence $2^k$, this shows that $f_0$ does extend to a meromorphic function on all of $\mathbb{C}$. However, this also shows that the meromorphic extension has poles at $z=2^k$ for all $k>0$, so it cannot be rational.
If I understand well, your question decomposes in two parts the second one being divided in two subparts
Q1) Is $f=\sum_{n=1}^{\infty} \frac{z^n}{2^n-1}$ rational ?
Q2) Let $\sum_{n=0}^{\infty} a_nz^n$ be a function
Q2.1) How to know if it is rational ?
Q2.2) How to check that it has simple pôles ?
Here are my answers (in part not different from what has been written though, save the last part).
R1) $f$ has radius of convergence $2$ because $\frac{1}{2^n-1}\sim_{n\mapsto +\infty} \frac{1}{2^n}$ and $$\sum_{n=1}^{\infty} \frac{z^n}{2^n}=\frac{2z}{2-z}$$ Computing $$ f(2z)=\sum_{n=1}^{\infty} \frac{2^nz^n}{2^n-1}=\sum_{n=1}^{\infty} \Big(1+\frac{1}{2^n-1}\Big) z^n $$ one gets easily $f(2z)=f(z)+\frac{z}{1-z}$ hence, after having checked that there is no cancellation of the pôle $1$, you get pôles at $\{2^n\}_{n\geq 0}$ which is impossible for a rational fraction.
R2) You use the shift operator. Here there is only one and this question, for several noncommutative series, is closely related to automata theory (see here, unfortunately in french) and the theory of Sweedler's, duals, see here. The (one step) shift operator reads
$$\sigma(f)=\frac{f-f(0)}{z}=\sum_{n\geq 0}a_{n+1}z^n\ .$$
Then iterate $$f,\sigma(f),\sigma^2(f),\cdots \sigma^n(f)\cdots $$ then either the orbit $\{\sigma^n(f)\}$ is of infinite rank and $f$ is not rational or $\{\sigma^n(f)\}$ it is of finite rank and you find a (first) $p$ such that $$ \sigma^p(f)=\sum_{j=0}^{p-1}\alpha_j\sigma^j(f) $$ the coefficients $\alpha_j$ being complex. Then, you write the transfer matrix $$ \begin{pmatrix} \sigma(f)\\ \sigma^2(f)\\ \vdots\\ \sigma^p(f) \end{pmatrix}= \begin{pmatrix} 0 & 1 & 0 & \cdots &\cdots\\ 0 & 0 & 1 & \cdots & \cdots\\ \vdots & \vdots & \ddots & \ddots &\vdots\\ \vdots & \ddots & \ddots & 0 &1\\ \alpha_0 & \cdots & \cdots & \alpha_{p-2} & \alpha_{p-1} \end{pmatrix} \begin{pmatrix} f\\ \sigma(f)\\ \vdots\\ \sigma^{p-1}(f) \end{pmatrix} $$ then the (non-zero) eigenvalues of $T$ (and their multiplicities) give you the (inverses of the) pôles of $f$ and their multiplicities.
A mini-example to illustrate the link between the non-zero spectrum of the transfer matrix and the poles.
Let $$ f=\sum_{n\geq 1} \frac{nz^n}{a^{n+1}},\ a\not=0 $$ then the shifts are $$ \sigma(f)=\sum_{n\geq 1} \frac{(n+1)z^n}{a^{n+2}},\ \sigma^2(f)=\sum_{n\geq 1} \frac{(n+2)z^n}{a^{n+3}} $$ which yields $$ \sigma^2(f)=\frac{2}{a}\sigma(f)-\frac{1}{a^2}f $$ the transfer matrix is then given by $$ \begin{pmatrix} \sigma(f)\\ \sigma^2(f)\\ \end{pmatrix}= \begin{pmatrix} 0 & 1\\ -\frac{1}{a^2} & \frac{2}{a} \end{pmatrix} \begin{pmatrix} f\\ \sigma(f) \end{pmatrix} $$ its characteristic polynomial is $(X-1/a)^2$.
In fact the fraction was $f=\frac{1}{(z-a)^2}$.
In Prudnikov, Brychkov, Marichev, vol. 1 there is an explicit formula via basic hypergeometric functions. Not rational.
