2
$\begingroup$

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?

$\endgroup$
  • 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$ – user40023 Nov 12 '15 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 Alexandersson Nov 12 '15 at 18:07
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.