Inspired by a [recent problem](https://mathoverflow.net/questions/66708/determining-a-recurrence-relation) for linear recurrence relations I have the following question (which may be too much to hope for). The [Catalan numbers](http://en.wikipedia.org/wiki/Catalan_number) (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.
> 
> 
> 



Determining a generating function (of a restricted form)
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.


