Recursions which define polynomials

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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}.$$