# Polynomials from a Recurrence Relation

Hi guys,

I have recently started looking at polynomials $q_n$ generated by initial choices $q_0=1$, $q_1=x$ with, for $n\geq 0$, some recurrence formula

$$q_{n+2}=xq_{n+1}+c_n q_n$$

where $c_n$ is some function in $n$. The first few of these are

$$q_2=x^2+c_0$$ $$q_3=x^3+(c_0+c_1)x$$ $$q_4=x^4+(c_0+c_1+c_2)x^2+c_2c_0$$ $$q_5=x^5+(c_0+c_1+c_2+c_3)x^3+(c_0c_2+c_0c_3+c_1c_3)x$$ $$q_6=x^6+(c_0+c_1+c_2+c_3+c_4)x^4+(c_0c_2+c_0c_3+c_0c_4+c_1c_3+c_1c_4+c_2c_4)x^2$$$$+c_0c_2c_4$$

My question is whether there is a name for the coefficients of the powers of $x$. I realise that they can be written as certain formulations of elementary symmetric polynomials but I am ideally looking for a reference where the specific expressions are studied

Any help would be great :)

-
I've added the tag orthogonal polynomials, that are related -orthogonal polynomials satisfy a three terms linear recurrence of a slightly more general form, and well characterized. Are you interested in the results with $any$ sequence $(c_n)$ or is your $(c_n)$ a particular sequence? (in which case it should be healthy to check if it corresponds to an orthogonal sequence). –  Pietro Majer Dec 30 '10 at 17:23
@ Pietro : Yes sorry, I should originally have tagged as relating to orthogonal polynomials. I am interested in general $c_n$, although I came to the recurrence relations from a number of specific examples which are well studied :) –  backstoreality Dec 30 '10 at 17:25

These polynomials are closely related to continuants, which arise in studying continuing fractions. The $n$th continuant of a sequence $a_0$, $a_1$, $\ldots$ is defined by $K(0)=1$, $K(1)=a_1$, $K(n)=a_n K(n-1) + K(n-2)$. They are sums of products of $a_1,\dots, a_n$ in which consecutive pairs are deleted. (See, for example, http://en.wikipedia.org/wiki/Continuant_(mathematics).)

Neither continuants nor the coefficients of the $c_n$ are symmetric polynomials; they cannot be expressed in terms of (or as "combinations of") elementary symmetric functions.

-
+1. There is no known closed-form evaluation for the matrix product $M_n=\prod_{k=1}^n[x,c_k;1,0]$ and even some kind of "understanding" its structure. If it were for $x=1$, then several hard conjectures in number theory about the continuants would be solved... –  Wadim Zudilin Dec 31 '10 at 4:49

Let's treat the $c_i$ as formal indeterminates.

Let $S(n,m)$ be the set of increasing functions $i:\{1,\ldots, m\}\to \{0,\ldots, n-2\}$, written $j \mapsto i_j$, such that $i_{j+1} > i_j + 1$ for all $j=1,\ldots, m$. So $S(n,m)$ is in bijection with the set of subsets of $\{0, \ldots, n-2\}$ of size $m$ which contain no adjacent pair $(k, k+1)$.

Then the coefficient of $x^{n - 2m}$ in $q_n$ is

$\sum_{i \in S(n,m)} c_{i_1} c_{i_2} \cdots c_{i_m}$

and all other coefficients are zero:

$q_n = \sum_{m = 0}^{[n/2]} \left( \sum_{i \in S(n,m)} c_{i_1} c_{i_2} \cdots c_{i_m} \right) x^{n - 2m}$.

Proof: induction on $n$.

Possibly considering the generating function $F = \sum_{n=0}^\infty q_nt^n$ may be helpful?

Note that these coefficients are not elementary symmetric polynomials in the $c_i$, since for example already $c_2c_0$ isn't invariant under all permutations of $\{0,1,2\}$. I just thought I'd spell out the symmetry that is involved here, and perhaps someone else knows a name for these coefficients.

-
@ Konstantin : Thanks for your reply and thanks for formally stating the weird symmetry that I hadn't yet put to paper :) Yes I should have been clearer in stating that I know that the coefficients are not elementary symmetric polynomials but they could probably written as combinations of them :) –  backstoreality Dec 30 '10 at 18:57