Going Backward

Now, at last, we can look at some theory. Let's start with the equation that defines the denominators.

q_n+1 = a_n+1q_n + q_n−1

If we rearrange it a little, it almost has forward-backward symmetry.

q_n+1 = q_n−1 + a_n+1q_n
q_n−1 = q_n+1 − a_n+1q_n

Hold that thought. We've gotten this far without a formal definition of what a purely repeating expansion is, but let's make one now. If we have a purely repeating expansion of length L, then we have two things. First, we have a set of coefficients a₀ through a_L−1. They have to be positive integers, even a₀, which in a normal expansion can be zero or negative, but they aren't otherwise constrained. Second, we have a rule that defines a_n for all other values of n.

a_n = a_(n mod L)

But, with the proper definition of what “mod” means, …

So, when I say “n mod m”, what I really mean is the number in the range [0,m−1] that identifies the congruence class that n belongs to.

… the same rule works for negative n, which means that we can return to the held thought and compute denominators backward as far as we like! Here's what that looks like for the large example, for the denominators that contain the upper chain. (Sorry the layout is a bit strange. The coefficient a_n+1 normally sits one space to the right of the denominator q_n that it multiplies, but after the rotation above, it sat one space below, and after the vertical reflection below, it sits one space above. For the first backward step here, for example, we compute 4638 as 19760 minus 2×7561.)

16		19760		2
15		7561		1
14		4638		1
13		2923		1
12		1715		1
11		1208		2
10		507		2
9		194		1
8		119		1
7		75		1
6		44		1
5		31		2
4		13		2
3		5		1
2		3		1
1		2		2
0		1		2
−1		0		1
−2		1		1
−3		−1		1
−4		2		1
−5		−3		2
−6		5		2
−7		−13		1
−8		31		1
−9		−44		1
−10		75		1
−11		−119		2
−12		194		2
−13		−507		1
−14		1208		1
−15		−1715		2
−16		2923		2
−17		−7561		1
−18		18045		1
−19		−25606		1
−20		43651		1

Surprise, there are the denominators that contain the lower chain! And some minus signs! Just by inspection, we can say that the upper denominator q_−n is equal to (−1)ⁿ times the lower denominator q_n−2. I wrote that sentence for positive n, but as you might guess, it's true for all values of n. For negative n, it describes how computing the lower denominators backward gives the upper denominators with alternating signs.

To put that another way, if we return to the point about forward-backward symmetry, it's pretty easy to see that multiplying the denominators by (−1)ⁿ has the same effect as reversing the direction of computation. So, if we take the complete bidirectional sequence of upper denominators, multiply by (−1)ⁿ, and also reverse the direction, we get another valid sequence of denominators, namely, the complete bidirectional sequence of lower denominators!

Let's also look briefly at the expansions and rotations that are involved.

2211112211221111 = expansion(7561)
2211221111221111
2111122111122112

The second and third lines show the rotations that produce the upper and lower denominators, respectively. Now, whenever we compute denominators, the first coefficient a₀ multiplies a denominator q₋₁ that is zero. But, in the bidirectional sequence of upper denominators, there's only one zero, so when we multiply by (−1)ⁿ and reverse the direction, the first coefficient for the upper denominators must become the first coefficient for the lower denominators. And, sure enough, if we read the second line backward starting from the first coefficient, we get the third line. (Note that the result of reading backward is first and foremost a reflection of the original expansion. It's only a rotation because of the third symmetry.)

It's too bad that the convention is to number the denominators from 0, because the results above would be nicer in several ways if the denominators were numbered from 1.

• The center point of the denominators, where q_n is zero, would be located not at n = −1 but rather at n = 0 … the center point of the integers!
• As a result, the upper denominator q_−n would be related to the lower denominator q_n (instead of q_n−2).
• The coefficient a_n and the denominator q_n that it would multiply would sit in the same space.
• As a result, the forward-backward symmetry would be even clearer.

That brings me to the last point I want to make about the bidirectional sequence of upper denominators. We know that the upper chain starts at position 36 in the upper denominators, and appears at every sixteenth position after that (since that's the repeat length of the expansion), and we know that the lower chain starts at position 42 in the lower denominators, which is position −44 in the upper denominators, and appears at every sixteenth position after that. But, the distance between 36 and −44 is divisible by sixteen. What do the intermediate denominators look like?

36		6684339842
20		294685
4		13
−12		194
−28		4400489
−44		99816291793

Surprise, there are the intermediate chain values! As before, I verified by experiment that the same things happen in general: when we compute the upper denominators backward, we find the lower denominators with alternating signs, and the intermediate denominators contain the intermediate chain values. The same things even happen for u = 1 and u = 2. In particular, when we compute the denominators backward, we find the same denominators with alternating signs. Those bidirectional denominators are the evidence that I was talking about earlier that there are two chains that happen to coincide.