# Recurrence relations with polynomial coefficients: an undecidable problem

I read once (somewhere) that solving a recurrence relation with polynomial coefficients, in the general case, is an undecidable problem. I can't remember the exact reference and I've been trying to prove it myself for some time now. Is anyone familiar with a paper or proof of this?

• It depends of what "solving" means. In Chapter 8 of the book "A = B", written by M. Petkovšek, H. S. Wilf, and D. Zeilberger, it is illustrate an algorithm to find if a recurrence with polynomial coefficient has a "closed form" in terms of hypergeometric functions or not. – user40023 Nov 12 '15 at 17:00
• Perhaps this is what you are looking for? arxiv.org/pdf/1203.0586v1.pdf The issue here is of course the nesting of a function, which in general makes a mess out of everything (for example, Julia sets etc. where several undecidable questions exists)... – Per Alexandersson Nov 12 '15 at 18:07

It is amazing how fast Maple, with the aid of this package, can compute asymptotics of solutions of linear recurrence equations with polynomial coefficients to any desired order. In particular, it can derive, very fast, the asymptotics for the number of involutions of size $n$, that probably took Moser and Wyman (Canadian J. Math. 7 (1955), 159--168) at least one month, and probably took Don Knuth (The Art of Computing Programming, vol. 3, 5.1.4) several hours.
The Birkhoff--Trjitzinsky method suffers from one drawback. It only does the asymptotics up to a multiplicative constant $C$. But nowadays this is hardly a problem. Just crank-out the first ten thousand terms of the sequence using the very recurrence whose asymptotics you are trying to find, not forgetting to furnish the few necessary initial conditions, and then estimate the constant empirically. If you are lucky, then Maple can recognize it in terms of "famous" constants like $e$ and $\pi$, by typing "identify(C);"