Recursions which define polynomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T10:13:44Z http://mathoverflow.net/feeds/question/21663 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21663/recursions-which-define-polynomials Recursions which define polynomials Wadim Zudilin 2010-04-17T13:08:01Z 2010-08-06T07:12:23Z <p>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. </p> <p><strong>Problem.</strong> 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.</p> <p>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)?</p> <p><strong>Edit.</strong> 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 <a href="http://people.brandeis.edu/~gessel/homepage/papers/superballot.pdf" rel="nofollow">[<em>J. Symbolic Computation</em> <strong>14</strong> (1992) 179--194]</a> addresses this combinatorial problem and gives several hypergeometric proofs of the integrality.</p> http://mathoverflow.net/questions/21663/recursions-which-define-polynomials/22713#22713 Answer by Johann Cigler for Recursions which define polynomials Johann Cigler 2010-04-27T11:56:51Z 2010-04-27T11:56:51Z <p>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). </p> <p>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</p> <p>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.</p> <p>Analogous results are true for powers of q-Fibonacci polynomials.</p> http://mathoverflow.net/questions/21663/recursions-which-define-polynomials/30196#30196 Answer by Max Alekseyev for Recursions which define polynomials Max Alekseyev 2010-07-01T15:38:47Z 2010-07-01T15:38:47Z <p>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.</p> <p>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> <p>$$P_n(t) = P_0(t) a(t)^n + \sum_{k=1}^n b_k(t) a(t)^{n-k}.$$</p> http://mathoverflow.net/questions/21663/recursions-which-define-polynomials/34729#34729 Answer by Ross Tang for Recursions which define polynomials Ross Tang 2010-08-06T05:15:28Z 2010-08-06T07:12:23Z <p>How about a simple relation like this?</p> <p><code>$$P_{n}(t) = \frac{P_{n-1}(t)}{1+t} + \frac{t}{1+t}$$</code></p> <p>with <code>$P_0(t) = 1$</code>, <code>$b_{n}(t) = t/(1+t)$</code> and <code>$a(t) = 1/(1+t)$</code>? The solution is <code>$P_n(t) = 1$</code> which is a polynomial with positive coefficient.</p> <p>Or another example:</p> <p><code>$P_{n}(t) = (1+t)^n$</code>, a(t) = 1/(1-t), <code>$b_n(t) = t^2(1+t)^{n-1}/(t-1)$</code></p> <p>In general, you can find examples quite easily, given that you have <code>$P_n(t)$</code> in mind, and function a(t) which is rational, and you solve for <code>$b_n(t)$</code>.</p> <p><code>$$b_n(t) = P_n(t)-a(t)P_{n-1}(t)$$</code></p> <p>As long as <code>$b_n(t)$</code> is rational as you required, you have a valid example.</p>