Simple and general relation between continuant polynomials

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

Continued fraction $[a_0,a_1,...,a_n]$ may be expressed as quotient of two polynomials of $(a_0,a_1,...,a_n)$, named continuants (see http://en.wikipedia.org/wiki/Continuant_%28mathematics%29 )

$[a_0,a_1,...,a_n] = K(a_0,a_1,...,a_n)/K(a_1,...,a_n)$

For example $K(a_0,a_1,a_2,a_3) = a_{0} a_{1} a_{2} a_{3} + a_{0} a_{1} + a_{0} a_{3} + a_{2} a_{3} + 1$

Continuants has many interesting recurrence relations some of which You may find in Graham, Knuth, Patashnik book "Concrete mathematics". Continuants appears for example in Hopcroft's minimization algorithm.

I found interesting relation:

$K( a_0,a_1,...,a_k,a_{(k+1)},...,a_n ) =$

$K(a_0,a_1,...,a_k,1,1,a_{(k+1)},...a_n) - K(a_0,a_1,...,a_k,1,a_{(k+1)},...a_n)$

that is - between variables $a_k$ and $a_{(k+1)}$ You put two of "1" in the firs and one "1" in the second term... You may consider this as generalisation of Fibonacci recurrence - because if You put all $a_i =1$ You obtain Fibonacci numbers.

For example: $K(a_0,a_1,a_2) = (a_0 a_ 1+1)a_2+a_0$ $K(a_0,a_1,1,1,a_2) = (2 a_0 a_1+ a_0+2)a_2+a_0 a_1+a_0+1$ $K(a_0,a_1,1,a_2) = (a_2+1)(a_0 a_1+1)+a_0 a_2$

And it is true that:

$K(a_0,a_1,a_2) = K(a_0,a_1,1,1,a_2) - K(a_0,a_1,1,a_2)$

I am curious - is this known fact? Or something new?

How to proove it - I found finite closed expression for continuant polynomial $K(a_0,a_1...a_n)$ in the form:

(1) $x = [a_{0},a_{1},a_{2},...a_{n}] =\frac{K(a_0,a_1,...,a_n)}{K(a_1,...,a_n)}= - \frac{1}{2} \frac{Tr \left( M(S- L) \right) }{Tr \left( M(S-T) \right) }$

where M is continuant matrix 2x2 and $S,T,L$ and $I$ (unity matrix) are constant matrices which form base in $SL(2,Z)$ space - they are defined in Sage workbook accesible for download here: http://fiksacie.wordpress.com/2012/03/17/ulamki-lancuchowe-nonstandard-matrix-representation-of-continued-fractions-cz-5/ There is also several essays about that on my blog - in polish. Proof is simple linear algebra exercise:

start from monoid formed by $S,T$ generators ( which represent in nonstandard way moves on Stern-Brocot tree - standard way consists of R-ight, and L-eft, RL matrices) and then construct ring over rationals with $I,S,T,L$ generators, and then formula above appears. M is defined as follows ( it is continuant matrix representation for given continued fraction $x = [a_{0},a_{1},a_{2},...a_{n}]$ )

(2) $M = S \prod_{i=0}^{n} S(ST)^{a_{i}}$.

$S$ is that $S^2 =I$ and $T$ is that $T^2 = I+T$ so

$I = T^2 -T = S(ST)S(ST) - S(ST)$

Then You may insert it in any place between $S(ST)^{a_{i}}S(ST)^{a_{i+1}}$ which gives expression above and many more if You consider $T^p$ for $p \in Z$ etc.

It is worth to note that in the general ring $Q[{I,S,T,L}]$ matrix $M$ has decomposition in the form $M=aI+bS+cT+dL$ with rational $a,b,c,d$ and that continued fractions form algebraic curve which equations is given by bilinear form $\left| w^TBw \right| = 1$ where $w=[a,b,c,d]$ - column vector where $a,b,c,d$ are integers (there are additional inequalities for this coefficients - because $M$ has to have positive elements)

Please note that (1) and (2) allows similarity transformations, and then You may choose any base in SL(2,Z) space and that whole construction may be easily generalized to bigger than 2x2 dimensional matrices. I have many questions here to ask, some of which are:

(A) are there irreducible representations of this construction in SL(D,Z) spaces where D>2?

(B) are there representations in complex number set ${z_1,...z_4}$ which obeys the same multiplication table as for $I,S,T,L$ matrices? How to express (1) in that case?

(C) probably there is possibility to construct pure algebraical representation in which continued fractions are generalised to values of operator which should be generalisation of rhs of (1). How to do it?

I am not professional mathematician - I have problems if it is worth to publish it, where to do it etc.

-

2
Does this not follow from the simple recursion for the continuant? – Gerry Myerson Mar 19 2012 at 21:50
I do not know. Does it? Could You show that? I develop my own way do generate it - from simple linear algebra... - let me explain in the post. – kakaz Mar 20 2012 at 8:27
Here is simplified and compact version of sage worksheet: sagenb.com/home/pub/4603 – kakaz Mar 23 2012 at 12:33

1 Answer

As Gerry remarked it follows from the recursion of the continuants. By the recurrence of the continuants you have ${K_{k + 3}}({a_0}, \cdots ,{a_k},1,1) = {K_{k + 2}}({a_0}, \cdots ,{a_k},1) + {K_{k + 1}}({a_0}, \cdots ,{a_k}).$ Therefore ${K_{k + 4}}({a_0}, \cdots ,{a_k},1,1,{a_{k + 1}}) = {a_{k + 1}}{K_{k + 3}}({a_0}, \cdots ,{a_k},1,1) + {K_{k + 2}}({a_0}, \cdots ,{a_k},1)$, ${K_{k + 3}}({a_0}, \cdots ,{a_k},1,{a_{k + 1}}) = {a_{k + 1}}{K_{k + 2}}({a_0}, \cdots ,{a_k},1) + {K_{k + 1}}({a_0}, \cdots ,{a_k}),$ ${K_{k + 2}}({a_0}, \cdots ,{a_k},{a_{k + 1}}) = {a_{k + 1}}{K_{k + 1}}({a_0}, \cdots ,{a_k}) + {K_k}({a_0}, \cdots ,{a_{k - 1}}).$ This implies ${K_{k + 4}}({a_0}, \cdots ,{a_k},1,1,{a_{k + 1}}) = {K_{k + 3}}({a_0}, \cdots ,{a_k},1,{a_{k + 1}}) + {K_{k + 2}}({a_0}, \cdots ,{a_k},{a_{k + 1}}).$ By induction your result follows.

-

Great! Thank You. So my result is somehow trivial... – kakaz Mar 20 2012 at 9:37
{"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": 45, "mathjax_display_tex": 0, "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": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "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.918070912361145, "perplexity_flag": "middle"}