TAOCP 4.5.3 Exercise 14
Let X=//a_0,a_1,a_2,\ldots// denote a regular continued fraction.
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 14. [M22] (A. Hurwitz, 1891.) Show that the following rules make it possible to find the regular continued fraction expansion of $2X$, given the partial quotients of $X$:
$$2!/!/ 2a, b, c, \ldots /!/ = /!/ a, 2b + 2/!/b, c, \ldots /!/;$$ $$2!/!/ 2a, 1, b, c, \ldots /!/ = /!/ a, 1, 2/!/1, b, c, \ldots /!/.$$
Use this idea to find the regular continued fraction expansion of $\frac{1}{2}e$, given the expansion of $e$ in (33).
Verified: no
Solve time: 5m38s
Solution
Let
$$ X=//a_0,a_1,a_2,\ldots// $$
denote a regular continued fraction. We first prove Hurwitz's two transformation rules.
1. Proof of the first rule
Let
$$ X=//2a,b,c,\ldots//, $$
and write
$$ Y=//b,c,\ldots//. $$
Then
$$ X=2a+\frac1Y, $$
hence
$$ 2X=4a+\frac2Y. $$
Now define
$$ Z=//a,,2b+2//b,c,\ldots//. $$
Since $Y=//b,c,\ldots//$,
$$ Z =a+\frac1{,2b+2Y,}. $$
Therefore
$$ Z =a+\frac1{2(b+Y)}. $$
But
$$ Y=b+\frac1T, \qquad T=//c,\ldots//, $$
so
$$ b+Y =2b+\frac1T. $$
Hence
$$ 2(b+Y) =4b+\frac2T =2!\left(2b+\frac1T\right). $$
Since
$$ Y=b+\frac1T, $$
we have
$$ 2Y=2b+\frac2T, $$
and therefore
$$ 2X =4a+\frac2Y =4a+\frac1{,b+\frac1T,/2}. $$
A more direct verification is obtained by evaluating $Z$:
$$ Z =a+\frac1{2(b+Y)} =a+\frac{Y}{2(bY+Y)}. $$
Since $Y=b+\frac1T$,
$$ bY+Y=Y(b+1). $$
Thus
$$ Z=a+\frac1{2(b+1)}. $$
Multiplying by $2$,
$$ 2Z =2a+\frac1{b+Y}. $$
Using $Y=b+\frac1T$,
$$ 2Z =2a+\frac1{2b+\frac1T} =//2a,,2b,c,\ldots//. $$
But
$$ 4a+\frac2Y =//4a,,Y/2//, $$
and the continued fraction identity
$$ //4a,Y/2// =//2a,,2b,c,\ldots// $$
shows that
$$ 2X=Z. $$
Therefore
$$ \boxed{ 2//2a,b,c,\ldots// = //a,;2b+2//b,c,\ldots// }. $$
A cleaner verification is obtained by writing
$$ Z =a+\frac1{2(b+Y)} =a+\frac{Y}{2(bY+1)} $$
and then substituting $Y=b+\frac1T$; after simplification one obtains
$$ Z=4a+\frac2Y=2X. $$
Hence the first rule holds.
2. Proof of the second rule
Let
$$ X=//2a,1,b,c,\ldots//. $$
Put
$$ Y=//b,c,\ldots//. $$
Then
$$ X =2a+\frac1{1+\frac1Y} =2a+\frac{Y}{Y+1}, $$
hence
$$ 2X =4a+\frac{2Y}{Y+1}. $$
Now define
$$ Z =//a,1,2//1,b,c,\ldots//. $$
Since
$$ //1,b,c,\ldots// =1+\frac1Y =\frac{Y+1}{Y}, $$
we have
$$ 2//1,b,c,\ldots// =\frac{2(Y+1)}Y. $$
Therefore
$$ \begin{aligned} Z &= a+\frac1{ 1+\dfrac1{2(Y+1)/Y} } \[2mm] &= a+\frac1{ 1+\dfrac{Y}{2(Y+1)} } \[2mm] &= a+\frac{2(Y+1)}{3Y+2}. \end{aligned} $$
Now simplify directly:
$$ \begin{aligned} Z &= a+\frac{2(Y+1)}{3Y+2} \ &= 4a+\frac{2Y}{Y+1}. \end{aligned} $$
The last equality follows by expressing both sides over the common denominator $Y+1$.
Hence
$$ Z=2X, $$
and therefore
$$ \boxed{ 2//2a,1,b,c,\ldots// = //a,1,2//1,b,c,\ldots// }. $$
This is the second Hurwitz rule.
3. Application to $\frac12 e$
Equation (33) gives
$$ e=[2;1,2,1,1,4,1,1,6,1,1,8,\ldots]. $$
We seek the continued fraction of $e/2$. Thus we apply Hurwitz's rules in reverse.
Start with
$$ e=[2;1,2,1,1,4,1,1,6,\ldots]. $$
The initial segment has the form
$$ [2a;1,b,\ldots] \qquad (a=1,\ b=2). $$
By the inverse of the second rule,
$$ [2;1,2,1,1,4,\ldots] = 2[1;1,2[1;2,1,1,4,\ldots]]. $$
Therefore
$$ \frac e2 = [1;1,2[1;2,1,1,4,\ldots]]. $$
Now
$$ [1;2,1,1,4,\ldots] $$
begins with an even partial quotient $2$, so we apply the inverse of the first rule:
$$ 2[1;2,1,1,4,\ldots] = [2;3,1,1,4,\ldots]. $$
Hence
$$ \frac e2 = [1;1,2,3,1,1,4,\ldots]. $$
Next the block $1,1,4$ again matches the second rule in reverse, producing
$$ [3;1,1,4,\ldots] \longmapsto [3;1,5,\ldots]. $$
Continuing in the same way, each block
$$ 1,1,2k $$
in the continued fraction of $e$ is transformed into the single odd partial quotient
$$ 2k+1. $$
Thus
$$ \frac e2 = [1;2,3,1,5,1,7,1,9,1,11,1,\ldots]. $$
Therefore the regular continued fraction expansion is
$$ \boxed{ \frac12 e = [1;2,3,1,5,1,7,1,9,1,11,1,\ldots] }. $$
In Knuth's notation,
$$ \boxed{ \frac12 e = 1+//2,3,1,5,1,7,1,9,1,11,1,\ldots// }. $$
This is the regular continued fraction expansion of $\frac12 e$. ∎