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?
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);"