Determining a generating function (of a restricted form)

Question

Inspired by a recent problem for linear recurrence relations I have the following question (which may be too much to hope for). The Catalan numbers (just to give a specific example) have generating function

$\frac{1-\sqrt{1-4x}}{2x}=1+x+2x^2+5x^3+14x^4+42x^5+132x^6+42x^7+1430x^8+4862x^9+\cdots$

Suppose I had the the first 20 or 50 terms of the left-hand size and wondered if there was an expression such as the right-hand side which agreed with it at least as far as I had? I would value answers in other forms but I'll ask about the following:

Given a finite integer sequence is there a reasonable procedure to discover if it might have a generating function of the form $\frac{p(x)+\sqrt{r(x)}}{q(x)}$ where $p,q,r$ are polynomials with many fewer coefficients between them than the length of the series.

Answer 1

In effect you're asking whether a given power series $y(x) = \sum_{n=0}^\infty a_n x^n$ satisfies a quadratic equation $a(x) y^2 + b(x) y + c(x) = 0$ with $a,b,c$ polynomials of low degree in $x$, say degree less than $\delta$. This is a linear system in $3\delta$ variables (the coefficients of $a,b,c$), so it's easy to test whether it has a nontrivial solution; and once you have several more than $3\delta$ coefficients of $y$ your linear system has several more equations than unknowns so the existence of a nontrivial solution is strong evidence that you've found the correct formula for $y$.

In the case of the Catalan numbers, if we take $\delta=2$ we're looking for a linear dependence among the sequences of coefficients of $1,x,y,xy,y^2,xy^2$, which are respectively

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...
0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, ...
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...
0, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

and in this simple case you'll find the linear relation $1 - y + xy^2 = 0$ "by inspection", but in any case a linear algebra package will find the corresponding dependence $(1, 0, -1, 0, 0, 1)$ automatically. Presumably that's what's done at some level by the seriestoalg routine that Richard Stanley recommends.

Naturally this idea works for finding dependencies whose degree in $y$, call it $d$, exceeds 2; for instance you can find a cubic over ${\bf Q}(x)$ satisfied by the generating function with $a_n = (3n)! / (n! (2n+1)!)$. [The proof is a standard exercise in residue calculus; for two elementary alternatives see my "one-page papers" at http://www.math.harvard.edu/~elkies/Misc/catalan.pdf and http://www.math.harvard.edu/~elkies/Misc/catalan2.pdf .]

For large $\delta$ there are algorithms for finding such relations that are more efficient than generic linear algebra, analogous to (but simpler than) the lattice reduction that's used for finding integer relations among real numbers known to some accuracy. I don't know if such an algorithm is implemented in seriestoalg or in another available package.

Answer 2

This sort of question was flogged half to death by D. Bailey some twenty five years ago, using lattice reduction techniques. I am sure there are other references, but see

http://crd.lbl.gov/~dhbailey/dhbpapers/pslq-cse.pdf