# Recursions which define polynomials

There are many examples (Somos sequences, special polynomials related to rational solutions of the Painleve equations) when a recurrence relation, which a priori produces a sequence of rational functions, in reality results in a polynomial sequence. In one of my last projects (joint work with Ole Warnaar) we "naturally" arrived at solution to the following problem which does not fit classes of sequences known to me.

Problem. The sequence of rational functions $P_0(t),P_1(t),\dots$ is defined by the recurrence relation $$P_n(t)=P_{n-1}(t)\cdot\frac{4t}{1+t}+\binom{2n}n\frac{1+t^{n+1}}{1+t} \quad\text{for n\ge1}$$ and initial condition $P_0(t)=1$. Show that $P_n(t)$ are polynomials with positive coefficients.

I know that Sloane's Encyclopedia of Integer Sequences allows one to guess the polynomials; proving then is a usual machinery. I wonder on what is actually known about nonhomogeneous recurrences $P_n(t)=a(t)P_{n-1}(t)+b_n(t)$, where $a(t)$ and $b_1(t),b_2(t),\dots$ are given rational functions and $a(t)$ is not a polynomial, whose solutions are polynomials. Have you seen other examples? For higher-order recursions? What about the positivity aspect (as in the problem above)?

Edit. In order to make my question complete, I add the solution to the problem: $$P_n(t)=\sum_{k=0}^nA_{k,n-k}t^k, \qquad\text{where}\quad A_{k,m}=\frac{(2k)!(2m)!}{k!(k+m)!m!}.$$ It is an exercise in number theory to verify that all $A_{k,m}$ are integers. These numbers are in a certain sense very close to the binomial coefficients $B_{k,m}=\dfrac{(k+m)!}{k!m!}$ (so that the analogue of $P_n(t)$ is $(1+t)^n$), although no combinatorial interpretation is known for general $k,m$. I. Gessel in [J. Symbolic Computation 14 (1992) 179--194] addresses this combinatorial problem and gives several hypergeometric proofs of the integrality.

-
If you replace "polynomials" with "rational functions" you could look up the Laurent phenomenon. arxiv.org/abs/math/0104241 –  john mangual Apr 17 '10 at 14:23
John, thanks for the hint. It's indeed an interesting piece, although related more to Somos sequences rather to my nonhomogeneous linear question. –  Wadim Zudilin Apr 17 '10 at 23:13
Could you expand a bit on what you expect? In the case at hand, if B(x) is the generating function for the bn, P(x) is just (B(x)+P0-b0)/(1-a x), so you could interpret Pn (roughly) as a B times a sequence of a's. Are you asking when these objects, with the objects in "B" and the object "a" having rational weights, have polynomial weight? Doesn't that sounds too general? –  Martin Rubey Apr 18 '10 at 7:50
I could not find any other example of a polynomial sequence generated in this way. I simply look for another such sequence of polynomials, so if you've ever seen something similar, please let me know. One more example would be a good answer to my question. –  Wadim Zudilin Apr 18 '10 at 23:08

I have no answer to your question, but some related examples. Consider the q-Fibonacci polynomials defined by f(0, x, s)=0, f(1, x, s)=1 and f(n, x, s)=x f(n-1, x, s)+q^(n-2) s f(n-2, x, s). Then the subsequences f(k n, x, s) satisfy a homogeneous recursion with rational coefficients which for k>2 are not polynomials (see e.g. my paper in arXiv 0806.0805).

More precisely f(k, x, q^k s) f(k n, x, s) – f(2 k, x, s) f(k (n-1), x, q^k s) +(-1)^k q^(k(3k-1)/2) s^k f(k, x, s) f(k (n-2), x, q^(2k) s)= 0 or equivalently

f(k, x, q^(n-2k) s) f(k n, x, s) – f(2 k, x, q^(k (n-2)) s) f(k (n-1), x, s) +(-1)^k q^(-k (3k+1)/2) q^(k^2 n) s^k f(k, x, q^(k (n-1)) s) f(k (n-2), x, s)= 0.

Analogous results are true for powers of q-Fibonacci polynomials.

-
@Johahn: thank you very much for this family of $q$-examples and the reference to your work on that. Even this is not an answer to my problem, the "integrality" phenomenon looks very similar. I have to think of this interesting direction as well. –  Wadim Zudilin Apr 27 '10 at 12:13
I had forgotten to mention that in the course of Gosper's algorithm such recursions occupy a prominent role, cf. the book a=b by Petkovsek, Wilf and Zeilberger. –  Johann Cigler Apr 28 '10 at 8:00

Multiplying the recurrence relation $P_n(t)=a(t)P_{n-1}(t)+b_n(t)$ by $x^n$ and summing up over $n=1,2,\dots,\infty$, we get $${\cal P}(x,t) - P_0(t) = a(t){\cal P}(x,t)x + {\cal B}(x,t)$$ where ${\cal P}(x,t) = \sum_{n=0}^{\infty} P_n(t) x^n$ and ${\cal B}(x,t) = \sum_{n=1}^{\infty} b_n(t) x^n$ are generating functions for $P_n(t)$ and $b_n(t)$ respectively.

Therefore, $${\cal P}(x,t) = \frac{{\cal B}(x,t) + P_0(t)}{1-a(t)x}$$ and $P_n(t)$ can be expressed as the coefficients of $x^n$ in the r.h.s., that is

$$P_n(t) = P_0(t) a(t)^n + \sum_{k=1}^n b_k(t) a(t)^{n-k}.$$

-
Max, I am sorry for being so late with your answer. Your formula indicates that it's quite unlikely to have $P_n(t)$ polynomials, isn't it? And your machinery could hardly prove the polynomiality for the above choice of $a(t)$ and $b_n(t)$. Can you give me some hints on how to generate (say, nontrivially) polynomials from your final formula, having a rational function $a(t)$? Thanks! –  Wadim Zudilin Jul 2 '10 at 9:08

How about a simple relation like this?

$$P_{n}(t) = \frac{P_{n-1}(t)}{1+t} + \frac{t}{1+t}$$

with $P_0(t) = 1$, $b_{n}(t) = t/(1+t)$ and $a(t) = 1/(1+t)$? The solution is $P_n(t) = 1$ which is a polynomial with positive coefficient.

Or another example:

$P_{n}(t) = (1+t)^n$, a(t) = 1/(1-t), $b_n(t) = t^2(1+t)^{n-1}/(t-1)$

In general, you can find examples quite easily, given that you have $P_n(t)$ in mind, and function a(t) which is rational, and you solve for $b_n(t)$.

$$b_n(t) = P_n(t)-a(t)P_{n-1}(t)$$

As long as $b_n(t)$ is rational as you required, you have a valid example.

-
Ross, this question is asking for recurrences for which there is no a priori reason for the solution to be polynomial, meaning that the result must be surprising in some sense. Your answer defeats this purpose, since you are devising the recurrence starting from a polynomial sequence. –  Gjergji Zaimi Aug 6 '10 at 7:17
"I could not find any other example of a polynomial sequence generated in this way. I simply look for another such sequence of polynomials, so if you've ever seen something similar, please let me know. One more example would be a good answer to my question.", from author's comment. He just asked for 1 more example. And there is no mention of surprise? –  Ross Tang Aug 6 '10 at 8:01
From another comment: "Can you give me some hints on how to generate (say, nontrivially) polynomials from your final formula, having a rational function a(t) ? Thanks! " He asked for method to generate polynomial from Max Alekseyev's formula. So I think providing a method is good enough. –  Ross Tang Aug 6 '10 at 8:03
I was merely suggesting that your answer is tautological for it is claiming that the recurrences which have polynomial solutions are the recurrences that are satisfied by a sequences of polynomials... –  Gjergji Zaimi Aug 6 '10 at 8:27