## Polynomials from a Recurrence Relation

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2010 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 2010 at 17:25

## 2 Answers

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
+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 2010 at 4:49

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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 2010 at 18:57
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 41, "mathjax_display_tex": 7, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9505389928817749, "perplexity_flag": "head"}