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