TAOCP 4.5.3 Exercise 32

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 32. [20] (a) A Morse code sequence of length $n$ is a string of $r$ dots and $s$ dashes, where $r + 2s = n$. For example, the Morse code sequences of length 4 are

$$\cdot\cdot\cdot\cdot,\quad -\cdot\cdot,\quad \cdot-\cdot,\quad \cdot\cdot-,\quad --$$

Noting that the continuant $K_4(x_1, x_2, x_3, x_4)$ is $x_1 x_2 x_3 x_4 + x_1 x_2 + x_1 x_4 + x_3 x_4 + 1$, find and prove a simple relation between $K_n(x_1, \ldots, x_n)$ and Morse code sequences of length $n$. (b) (L. Euler, Novi Comm. Acad. Sci. Pet. 9 (1762), 53–69.) Prove that

$$K_{m+n}(x_1, \ldots, x_{m+n}) = K_m(x_1, \ldots, x_m) K_n(x_{m+1}, \ldots, x_{m+n})$$ $$+ K_{m-1}(x_1, \ldots, x_{m-1}) K_{n-1}(x_{m+2}, \ldots, x_{m+n}).$$

Verified: yes
Solve time: 1m32s

---

Solution

(a)

Associate the positions $1,2,\ldots,n$ with the variables $x_1,x_2,\ldots,x_n$.

A Morse code sequence of length $n$ may be regarded as a tiling of the interval ${1,\ldots,n}$ by

• dots, covering one position;
• dashes, covering two consecutive positions.

For such a tiling $M$, define its weight by

$$ w(M)=\prod_{i\in D(M)} x_i, $$

where $D(M)$ is the set of positions occupied by dots. Positions belonging to dashes contribute no factor.

The required relation is

$$ K_n(x_1,\ldots,x_n) = \sum_{M} w(M), \tag{1} $$

where the sum extends over all Morse code sequences of length $n$.

To prove this, compare (1) with Euler's description of continuants given before (5). Starting with the product

$$ x_1x_2\cdots x_n, $$

a term of $K_n$ is obtained by deleting zero or more nonoverlapping pairs

$$ x_jx_{j+1}. $$

Choose a dash covering positions $j$ and $j+1$ whenever the pair $x_jx_{j+1}$ is deleted. Since the deleted pairs are nonoverlapping, the chosen dashes do not overlap. Every position not belonging to a dash is represented by a dot.

This construction produces a unique Morse code sequence of length $n$. The resulting monomial is precisely the product of the variables corresponding to dot positions. Conversely, every Morse code sequence determines a unique set of nonoverlapping deleted pairs, hence a unique term of $K_n$.

Therefore the monomials occurring in $K_n$ are in one-to-one correspondence with Morse code sequences of length $n$, and each monomial is exactly the weight defined above. Formula (1) follows.

For example,

$$ K_4=x_1x_2x_3x_4+x_1x_2+x_1x_4+x_3x_4+1, $$

corresponding respectively to

$$ \cdot\cdot\cdot\cdot,\qquad -\cdot\cdot,\qquad \cdot-\cdot,\qquad \cdot\cdot-,\qquad --. $$

This completes the proof.

∎

(b)

Using the interpretation of part (a), consider all Morse code sequences of length $m+n$.

Partition them into two classes.

First, suppose no dash crosses the boundary between positions $m$ and $m+1$. Then the portion in positions $1,\ldots,m$ is an arbitrary Morse code sequence of length $m$, and the portion in positions $m+1,\ldots,m+n$ is an arbitrary Morse code sequence of length $n$. By part (a), the sum of the corresponding weights is

$$ K_m(x_1,\ldots,x_m), K_n(x_{m+1},\ldots,x_{m+n}). $$

Second, suppose a dash does cross the boundary. Since a dash has length $2$, it must cover exactly positions $m$ and $m+1$. Removing this dash leaves

• an arbitrary Morse code sequence of length $m-1$ on positions $1,\ldots,m-1$;
• an arbitrary Morse code sequence of length $n-1$ on positions $m+2,\ldots,m+n$.

Because the boundary dash contributes no variable factors, the total weight of this class is

$$ K_{m-1}(x_1,\ldots,x_{m-1}), K_{n-1}(x_{m+2},\ldots,x_{m+n}). $$

The two classes are disjoint and exhaust all Morse code sequences of length $m+n$. Summing their weights and applying part (a) yields

$$ K_{m+n}(x_1,\ldots,x_{m+n}) = K_m(x_1,\ldots,x_m), K_n(x_{m+1},\ldots,x_{m+n}) $$

$$ \qquad\qquad + K_{m-1}(x_1,\ldots,x_{m-1}), K_{n-1}(x_{m+2},\ldots,x_{m+n}). $$

Hence

$$ \boxed{ K_{m+n}(x_1,\ldots,x_{m+n}) = K_m(x_1,\ldots,x_m)K_n(x_{m+1},\ldots,x_{m+n}) + K_{m-1}(x_1,\ldots,x_{m-1})K_{n-1}(x_{m+2},\ldots,x_{m+n}) }. $$

This completes the proof.

∎