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.

$\endgroup$
4
  • 1
    $\begingroup$ If your hypothesis is true, then you should have the term $q_5q_6r_7$. Was that missing in your computation or does that disprove the hypothesis? Also, I would expect that you would get an empty product for the three deletions, which would give you $1r_7$ so you might have trouble there, too. The combinatorist in me really wants your hypothesis to be true though, because then we could count the number of terms as the fibonacci numbers! $\endgroup$ – William Macrae Nov 26 '12 at 3:09
  • $\begingroup$ @WilliamMacrae Oh, yes! I do believe I am missing those terms above. It's really tedious to do this by hand, and I don't know off-hand how to go about doing something like this programmatically. I've edited it to be (hopefully) correct now. $\endgroup$ – providence Nov 26 '12 at 3:27
  • 1
    $\begingroup$ Wonderful. Unfortunately my number theory isn't enough to actually address the question, but to expand on the Fibonacci comment, the subsets you present are the complements of the vertices in matchings in $P_6$, so there are as many as there are matchings in $P_6$. It's also easy to argue this directly with a recurrence, and you might think of it as partial tilings of a $1 \times 6$ grid with $1 \times 2$ dominoes. The squares that are not covered correspond to the $q$s in the term. In short, these correspond to many of the descriptions of what fibonacci numbers count: oeis.org/A000045 $\endgroup$ – William Macrae Nov 26 '12 at 3:46
  • 4
    $\begingroup$ These polynomials are called continuants, and you may find more information by searching for that word. $\endgroup$ – Gerry Myerson Nov 26 '12 at 3:47
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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