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? 
 A: Even computing the asymptotics of solutions of linear recurrence equations with polynomial coefficients is an open problem! From 
[D.~Zeilberger,
AsyRec: A Maple package for computing the asymptotics of solutions of linear recurrence equations with polynomial coefficients,
Personal Journal of Ekhad and Zeilberger (4 April 2008), 2~pp.]:

I did not know much about computer algebra systems.  Now that I do, I
  thought that it is about time to write a Maple implementation of the
  Birkhoff--Trjitzinsky method so lucidly described in that paper.
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.
Just type: "Asy(N**2-N-(n+1),n,N,10);", to get the asymptotics up to
  the 10th order.
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);"

