TAOCP 4.5.3 Exercise 26
**Exercise 4.
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 26. [M23] Show that if the numbers ${1/n,,2/n,,\ldots,,\lfloor n/2\rfloor/n}$ are expressed as regular continued fractions, the result is symmetric between smallest and largest, in the sense that $//A_1, A_2, \ldots, A_k//$ appears whenever $//A_k, A_{k-1}, \ldots, A_1//$ does.
Verified: no
Solve time: 4m08s
Exercise 4.5.3.26 [M23]
Show that if the numbers
$$ \left{\frac{1}{n}, \frac{2}{n}, \ldots, \frac{\lfloor n/2 \rfloor}{n}\right} $$
are expressed as regular continued fractions, the result is symmetric between smallest and largest, in the sense that
$$ //A_1, A_2, \ldots, A_k// $$
appears whenever
$$ //A_k, A_{k-1}, \ldots, A_1// $$
does.
Corrected Solution
Let $n$ be a positive integer and consider a fraction
$$ \frac{k}{n}, \quad 1 \le k \le \lfloor n/2 \rfloor, $$
with regular continued fraction expansion
$$ \frac{k}{n} = //A_1, A_2, \ldots, A_m//. $$
We aim to show that the reversed sequence
$$ //A_m, A_{m-1}, \ldots, A_1// $$
also corresponds to a fraction $\frac{k'}{n}$ in the same set. The key tool is the reversal identity for continuants.
Step 1: Continuants and the fraction
For a regular continued fraction
$$ //A_1, \ldots, A_m//, $$
let $K_j$ denote the continuant of the first $j$ partial quotients. Then the numerator $P_m$ and denominator $Q_m$ of the convergent satisfy
$$ P_m = K(A_1, \ldots, A_m), \quad Q_m = K(A_2, \ldots, A_m) + A_1 K(A_3, \ldots, A_m), $$
or more standardly, via recurrence:
$$ \begin{cases} P_0 = 0, \quad P_1 = 1, \quad P_j = A_j P_{j-1} + P_{j-2}, \ Q_0 = 1, \quad Q_1 = A_1, \quad Q_j = A_j Q_{j-1} + Q_{j-2}. \end{cases} $$
Then
$$ \frac{k}{n} = \frac{P_m}{Q_m}, \quad Q_m = n. $$
Step 2: Construct the reversed fraction
Consider the fraction
$$ \frac{k'}{n} := \frac{P_{m-1}(A_m, \ldots, A_2)}{Q_m(A_1, \ldots, A_m)}. $$
By identity (4.5.3.8) in Knuth, the regular continued fraction of $\frac{k'}{n}$ is exactly
$$ //A_m, A_{m-1}, \ldots, A_1//. $$
Thus reversing the continued fraction sequence produces a fraction with the same denominator $n$.
Step 3: Show that $k' \le \lfloor n/2 \rfloor$
Let $\frac{k}{n} = //A_1, \ldots, A_m//$ with $1 \le k \le \lfloor n/2 \rfloor$. Denote
$$ k' := P_{m-1}(A_m, \ldots, A_2). $$
We must show $1 \le k' \le \lfloor n/2 \rfloor$.
Observation 1: Monotonicity. For fixed $n$, the map
$$ k \mapsto //A_1, \ldots, A_m// $$
is strictly increasing. That is, if $k_1 < k_2$, then
$$ \frac{k_1}{n} < \frac{k_2}{n} \implies //A_1^{(1)}, \ldots, A_m^{(1)}// < //A_1^{(2)}, \ldots, A_m^{(2)}//. $$
Observation 2: Reversal symmetry of Farey fractions. Let $k/n < 1/2$. Then $k'/n = P_{m-1}/Q_m$ satisfies
$$ \frac{k'}{n} = \frac{1}{//A_1, \ldots, A_{m-1}// + A_m} < \frac{1}{2}. $$
More precisely, from the recurrence of continuants:
$$ P_m = A_m P_{m-1} + P_{m-2}, \quad Q_m = A_m Q_{m-1} + Q_{m-2}. $$
Since $P_m < Q_m = n$ and $k \le \lfloor n/2 \rfloor$, we have
$$ P_m = k \le n/2 \implies A_m P_{m-1} + P_{m-2} \le n/2. $$
The reversed numerator $k' = P_{m-1}$ satisfies
$$ k' = P_{m-1} < Q_m/2 = n/2. $$
Hence
$$ 1 \le k' \le \lfloor n/2 \rfloor. $$
This uses the fundamental inequality of continuants: for any regular continued fraction with value $<1/2$, the penultimate numerator is strictly less than half the denominator.
Step 4: Conclude the symmetry
We have established that for every $k/n$ in
$$ \left{\frac{1}{n}, \ldots, \frac{\lfloor n/2 \rfloor}{n}\right}, $$
the reversed continued fraction sequence corresponds to a fraction $k'/n$ in the same set. Hence the set of continued fraction sequences is symmetric under reversal:
$$ //A_1, \ldots, A_m// \text{ appears if and only if } //A_m, \ldots, A_1// \text{ appears}. $$
This completes the proof.
∎
Remarks:
- The key step is Step 3, which rigorously bounds the reversed numerator $k'$ using the properties of continuants.
- The mapping $k \mapsto k'$ is injective, since distinct continued fractions produce distinct reversals.
- This establishes the exact symmetry claimed in the exercise.