Skip to main content
MathOverflow

Return to Answer

deleted 22 characters in body
Source Link
Qiaochu Yuan
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

$\sum a_n z^n$ is a rational function iff $a_n$ is a (finite) sum of products of a polynomial and an exponentialpolynomials 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.

$\sum a_n z^n$ is a rational function iff $a_n$ is a (finite) sum of products of a polynomial and an exponential. 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.

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

Source Link
Qiaochu Yuan
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

$\sum a_n z^n$ is a rational function iff $a_n$ is a (finite) sum of products of a polynomial and an exponential. 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.