MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :)

share|cite|improve this question
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,

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.

share|cite|improve this answer
+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.

share|cite|improve this answer
@ 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.