3
$\begingroup$

I was playing around with the Euclidean algorithm when I noticed the following. Assume that some number $r_1$ breaks down via the Euclidean algorithm as follows:

$ r_1 = q_1r_2 + r_3 \\ r_2 = q_2r_3 + r_4 \\ r_3 = q_3r_4 + r_5 \\ \vdots \\ r_{k-1} = q_{k-1}r_{k} + r_{k+1}\\ r_k = q_kr_{k+1}$

Then, if we write $r_1$ in terms $r_{k+1}$ we will get something that looks like

$ r_1 = q_1(q_2( \cdots (q_{k-1}(q_kr_{k+1}) + r_k) + r_{k - 1}) \cdots ) + r_4) + r_3$

Now, actually figuring out what that looks like after expansion with regards to coefficients on $r_{k + 1}$ is rather mind-bending (for me at least), so I'll give a concrete example for $k = 6$:

$ r_1 = q_1q_2q_3q_4q_5q_6r_7 + q_1q_2q_3q_4r_7 + q_1q_2q_3q_6r_7 + q_1q_2q_5q_6r_7 + q_1q_2r_7 + q_1q_4q_5q_6r_7 + q_1q_4r_7 + q_1q_6r_7 + q_3q_4q_5q_6r_7 + q_3q_4r_7 + q_3q_6r_7 + q_5q_6r_7 + r_7$

I really hope I did that correctly, because I noticed a neat pattern. The subscripts on the $q$'s form all the ways of deleting two consecutive elements from the sequence $S = 1, 2, 3, 4, 5, 6$ union with all the ways of performing two deletions of two consecutive elements of $S$. The "empty sum" $0r_7$, or the only way to perform three deletions of two consecutive elements from $S$ is included as well, I suppose.

In other words, the family of sets of $q$-subscripts on summands above is:

$\{\{1, 2, 3, 4, 5, 6\}, \{1, 2, 3, 4\}, \{1, 2, 3, 6\}, \{1, 2, 5, 6\}, \{1, 2\}, \{1, 4, 5, 6\}, \{1, 4,\}, \{1, 6\}, \{3, 4, 5, 6\}, \{3, 4\}, \{3, 6\}, \{5, 6\}, \emptyset\}$

The Question Does the above mean anything? If so, what in the world did I find? Do I need to go outside more often?

P.S. Seeing as I don't really know what I'm asking for, I may be tagging this incorrectly. Please edit tags if you feel it necessary.

  • 4
    These polynomials are called *continuants*, and you may find more information by searching for that word.2012-11-26

1 Answers 1

1

A direct way to see your result:

When you try to express $r_1$ with $r_7$, then you can view the sum at each step as a decision process:

Either I choose to increase the index $i$ by one and record the appropriate $q_i$ or I choose to increase the index by two.

After some time, I arrive at $r_7$, and my list of $q$s tell me exactly what choices I made, so that there is a bijection between the choices and the terms in the final expression.

Now, each time I choose to increase the index by two, I decide to not take $q_i$, but I also cannot take $q_{i+1}$ because I jump over the point where I could make this choice. This corresponds exactly to removing the two consecutive values $i$, $i+1$ from the product $q_1q_2 \dots q_7$ and this is the only restriction because after the jump I can again choose freely whether to take the next $q$.

Therefore, your observation is indeed true.


To see the relation to Fibonacci numbers, start from the bottom and set $q_i=1$ for all $i$ and $r_n=1$. Clearly, $r_{n+1}=0$. Now, you have exactly the recurrence for Fibonacci numbers $F_{k}=F_{k-1}+F_{k-2}$.

Since each term in your expansion is 1 if $q_i=1$, the Fibonacci numbers count the number of terms in your expression.


This answer should not discourage you from following Gerry Myerson's advice to read up on continuants to learn more.