TAOCP 4.5.3 Exercise 9

Exercise 9. [**] [M21] Show that continued fractions satisfy the following identities:

a) $//x_1, \ldots, x_n// = //x_1, \ldots, x_k + //x_{k+1}, \ldots, x_n///, \quad 1 \le k \le n;$

b) $//0, x_1, x_2, \ldots, x_n// = x_1 + //x_2, \ldots, x_n//, \quad n \ge 1;$

c) $//x_1, \ldots, x_{k-1}, x_k, 0, x_{k+1}, x_{k+2}, \ldots, x_n// = //x_1, \ldots, x_{k-1}, x_k + x_{k+1}, x_{k+2}, \ldots, x_n//,$

$\quad 1 \le k < n;$

d) $1 - //x_1, x_2, \ldots, x_n// = //1, x_1 - 1, x_2, \ldots, x_n//, \quad n \ge 1.$

Verified: yes
Solve time: 1m38s

For (a), write

$$ T=//x_{k+1},\ldots,x_n//. $$

By definition (2),

$$ T=\frac1{x_{k+1}+\frac1{\cdots+\frac1{x_n}}}, $$

hence

$$ \frac1{x_k+T} =\frac1{x_k+\frac1{x_{k+1}+\frac1{\cdots+\frac1{x_n}}}} =//x_k,x_{k+1},\ldots,x_n//. $$

Substituting this expression for the tail of the continued fraction gives

$$ //x_1,\ldots,x_n// =//x_1,\ldots,x_k+//x_{k+1},\ldots,x_n///. $$

For (b),

$$ //0,x_1,\ldots,x_n// =\frac1{0+\frac1{x_1+\frac1{\cdots+\frac1{x_n}}}} =x_1+//x_2,\ldots,x_n//. $$

For (c),

$$ //x_k,0,x_{k+1}// =\frac1{x_k+\frac1{0+\frac1{x_{k+1}}}} =\frac1{x_k+x_{k+1}}, $$

so replacing the block $(x_k,0,x_{k+1})$ by $x_k+x_{k+1}$ leaves the continued fraction unchanged:

$$ //x_1,\ldots,x_{k-1},x_k,0,x_{k+1},x_{k+2},\ldots,x_n// = //x_1,\ldots,x_{k-1},x_k+x_{k+1},x_{k+2},\ldots,x_n//. $$

For (d),

$$ 1-//x_1,\ldots,x_n// =1-\frac1{x_1+//x_2,\ldots,x_n//} =\frac{x_1-1+//x_2,\ldots,x_n//}{x_1+//x_2,\ldots,x_n//}. $$

Also,

$$ //1,x_1-1,x_2,\ldots,x_n// =\frac1{1+\frac1{x_1-1+//x_2,\ldots,x_n//}} =\frac{x_1-1+//x_2,\ldots,x_n//}{x_1+//x_2,\ldots,x_n//}. $$

The two expressions are equal, proving

$$ 1-//x_1,x_2,\ldots,x_n// = //1,x_1-1,x_2,\ldots,x_n//. $$

This completes the proof.

∎