Triangles

That same fact, plus the fact that q₋₁ is always zero, plus the recurrence relation … together they completely explain the second observation near the end of the first part.

The denominators at n = 15 are the same (7561!) and the denominators at n = 31 are the same. That pattern continues: in every sixteenth row, the denominators are the same.

What about the first observation?

The denominators up to 2923 are the same, although offset by one row.

Well, let's run the second algorithm on both the expansion [a₀,2] and its improper form [a₀,1,1].

		a0	2
0	1	a0	2a0 + 1
1	0	1	2
		a0	1	1
0	1	a0	a0 + 1	2a0 + 1
1	0	1	1	2

Because an improper form leads to the same number, the last numerators and the last denominators are guaranteed to be the same, but here the next-to-last denominators are also the same. However, the equation that defines the denominators only looks back two spaces, so if we take an arbitrary suffix and append it to the two expansions, we'll continue to get the same denominators. And that's exactly why the denominators up to 2923 are the same!

0		1		2		1		2
1		1		1		2		2
2		2		1
						3		1
3		3		1		5		1
4		5		1		13		2
5		13		2		31		2
6		31		2		44		1
7		44		1		75		1
8		75		1		119		1
9		119		1		194		1
10		194		1		507		2
11		507		2		1208		2
12		1208		2		1715		1
13		1715		1		2923		1
14		2923		1
						4638		1
15		7561		2		7561		1

At the top we have the shared first coefficient a₀ = 2 of the upper and lower expansions. Next we have an improper-proper triangle that leaves the last two denominators the same. In the middle we have the “arbitrary suffix”. It's forced to have reflection symmetry by the fact that the lower expansion is just the upper expansion backward. And, at the bottom we have a proper-improper triangle that conveniently produces the same final denominator u.

Do the expansions for other solutions have the same structure? A quick experiment says yes, with one caveat. In the table above, the right side is ahead of the left. But, a closer look at the table of positions reveals that that happens exactly when δ = +1. To make the other case δ = −1 possible, we need to allow the sides to be exchanged so that the left side is ahead of the right.

Next I'd like to briefly acknowledge a strange thing.

2211112211221111 = expansion(7561)
2211221111221111
2211221111221111

The second and third lines both show the upper expansion. If we remove the surrounding 22 and 11, we're left with the middle part that has reflection symmetry. The second line shows that. But, if we don't remove the surrounding 22 and 11, the whole thing also has reflection symmetry … or, rather, has two rotations that have reflection symmetry. The third line shows the relevant half-expansion. I really don't understand how the two reflection symmetries can coexist.

Finally, let's generalize a bit and consider the expansion [a₀, a₁] (with a₁ > 2) and two variants.

		a0	a1
0	1	a0	a0a1 + 1
1	0	1	a1
		a0	a1 − 1	1
0	1	a0	a0a1 − a0 + 1	a0a1 + 1
1	0	1	a1 − 1	a1
		a0	1	a1 − 1
0	1	a0	a0 + 1	a0a1 + a1 − 1
1	0	1	1	a1

The variant [a₀, a₁−1, 1] is just the improper form. It has the same last numerator and last denominator as the original expansion, of course, but the next-to-last denominator is different.

I'll call the variant [a₀, 1, a₁−1] the same-denominator form. It has the same last denominator and next-to-last denominator as the original expansion, but the last numerator is different.

With longer expansions, an important difference emerges. We get the improper form by changing the end of the original expansion, but we get the same-denominator form by changing the start.

[a₀, a₁, a₂, a₃, a₄, a₅−1, 1]
[a₀, 1, a₁−1, a₂, a₃, a₄, a₅]

Another difference is that there are only two ways to get the same last numerator and last denominator, but there are an infinite number of ways (times two) to get the same last denominator and next-to-last denominator because changing a₀ doesn't affect denominators.

It's pretty easy to put together a direct proof that there are no other ways to get the same last denominator and next-to-last denominator, but let's take a more illuminating approach. Remember the equation for the approximation quality Q_n from way back in Two Examples?

Once I knew what I was looking for, though, I was able to find the correct exact equation in [Hua] after all. It was just a few lines of algebra in another proof, not even presented as a result!

Qn	=		[an+1, an+2, an+3, … ]
		+	[0, an, an−1, an−2, … , a3, a2, a1]

Let's look at some of that algebra.

pn	/	qn = [a0,	a1, a2, a3, … , an−2, an−1, an]
qn−1	/	qn = [0,	an, an−1, an−2, … , a3, a2, a1]

If we compute the numerators and denominators for an expansion in the usual way (the first line), then the ratio of the last two denominators is equal to the reversed expansion with 0 added and a₀ removed. That sounds like it ought to be a deep result, but it's essentially just the equation that defines the denominators …

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

… divided by q_n.

Now suppose we have two expansions. If the last denominators and the next-to-last denominators are the same, then the ratios are equal, so the reversed expansions are equal as numbers, so either they're equal as lists of coefficients or one is the improper form of the other. Therefore, if we exclude a₀ from the comparisons, then either the original expansions are equal as lists of coefficients or one is the same-denominator form of the other!

The equation for negative numbers from Equivalence is a nice example to keep in mind, by the way.

−[a₀, a₁, a₂, a₃, … ] = [−a₀−1, 1, a₁−1, a₂, a₃, … ]

That brings us to the point of the whole generalization. Now that we know more, the top triangle is obviously a same-denominator triangle, not an improper-proper triangle.