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.