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?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ 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. $\endgroup$– user40023Commented Nov 12, 2015 at 17:00
-
1$\begingroup$ 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)... $\endgroup$– Per AlexanderssonCommented Nov 12, 2015 at 18:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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);"
answered Nov 13, 2015 at 11:02