TAOCP 1.2.8 Exercise 36

Let S_1=\text{a},\quad S_2=\text{b},\quad S_{n+2}=S_{n+1}S_n \quad (n\ge1), so that

taocpmathematicsalgorithmsvolume-1math-hard

Section 1.2.8: Fibonacci Numbers

Exercise 36. [M32] (Fibonacci strings.) Let $S_1=\text{"a"}$, $S_2=\text{"b"}$, and $S_{n+2}=S_{n+1}S_n$, $n>0$; in other words, $S_{n+2}$ is formed by placing $S_n$ at the right of $S_{n+1}$. We have $S_3=\text{"ba"}$, $S_4=\text{"bab"}$, $S_5=\text{"babba"}$, etc. Clearly $S_n$ has $F_n$ letters. Explore the properties of $S_n$. (Where do double letters occur? Can you predict the value of the $k$th letter of $S_n$? What is the density of the b's? And so on.)

Verified: yes
Solve time: 8m27s

Exercise 1.2.8.36, Fibonacci strings

Let

$$ S_1=\text{a},\quad S_2=\text{b},\quad S_{n+2}=S_{n+1}S_n \quad (n\ge1), $$

so that

$$ S_3=\text{ba},\quad S_4=\text{bab},\quad S_5=\text{babba},\quad S_6=\text{babbabab},\dots $$

Denote the length of $S_n$ by $|S_n|$. Let

$$ A_n=#{\text{a's in }S_n},\quad B_n=#{\text{b's in }S_n}. $$

We explore structural properties of these strings: lengths, first and last letters, double letters, the $k$th letter, and limiting densities.

1. Lengths

Since $S_{n+2}=S_{n+1}S_n$, the lengths satisfy

$$ |S_{n+2}|=|S_{n+1}|+|S_n|, \quad |S_1|=|S_2|=1. $$

By induction, $|S_n|=F_n$, the $n$th Fibonacci number with the convention $F_1=F_2=1$.

2. Letter counts

Similarly, the numbers of $a$'s and $b$'s satisfy

$$ A_{n+2}=A_{n+1}+A_n,\quad B_{n+2}=B_{n+1}+B_n, $$

with initial conditions $A_1=1, A_2=0$ and $B_1=0, B_2=1$. Hence, by induction,

$$ A_n=F_{n-1},\quad B_n=F_{n-2} \quad (n\ge2), $$

consistent with the Fibonacci recurrence.

3. First and last letters

First letter

We prove by induction that for $n\ge2$, the first letter of $S_n$ is $b$:

  • Base cases: $S_2=\text{b}$, $S_3=\text{ba}$ have first letter $b$.
  • Inductive step: If $S_n$ and $S_{n+1}$ begin with $b$, then $S_{n+2}=S_{n+1}S_n$ also begins with $b$.

Last letter

Since $S_{n+2}=S_{n+1}S_n$, the last letter of $S_{n+2}$ is the last letter of $S_n$. With $S_1=\text{a}$ and $S_2=\text{b}$, we have

$$ \text{last}(S_n)= \begin{cases} \text{a}, & n\text{ odd},\ \text{b}, & n\text{ even}. \end{cases} $$

4. Double letters

Absence of $aa$

No $aa$ occurs in $S_n$ for any $n\ge1$:

  • Base cases: $S_1, S_2$ contain no $aa$.
  • Inductive step: If $S_n$ and $S_{n+1}$ contain no $aa$, then $S_{n+2}=S_{n+1}S_n$ can only introduce $aa$ at the junction. But $\text{last}(S_{n+1})=\text{a}$ occurs only if $n+1$ is odd, and $\text{first}(S_n)=b$ for $n\ge2$, so the junction cannot produce $aa$.

Occurrence of $bb$

A new $bb$ is created at the junction $S_{n+2}=S_{n+1}S_n$ if and only if $\text{last}(S_{n+1})=\text{b}$ and $\text{first}(S_n)=\text{b}$. Since $\text{first}(S_n)=b$ for $n\ge2$ and $\text{last}(S_{n+1})=b$ if $n+1$ is even, the junction creates $bb$ exactly when $n$ is odd.

By iterating this reasoning, all occurrences of $bb$ can be traced recursively to junctions corresponding to odd indices. More precisely, a $bb$ occurs at positions corresponding to the end of an $S_m$ with odd $m$ concatenated with $S_{m-1}$. Thus, $bb$'s occur at predictable Fibonacci-related positions.

5. Determination of the $k$th letter

Let $w_n(k)$ denote the $k$th letter of $S_n$ for $1\le k\le F_n$, and let $w(k)$ denote the $k$th letter in the infinite Fibonacci word

$$ S_\infty=\lim_{n\to\infty} S_n. $$

From the decomposition $S_n=S_{n-1}S_{n-2}$, we have the recursion

$$ w_n(k)= \begin{cases} w_{n-1}(k), & 1\le k\le F_{n-1},\ w_{n-2}(k-F_{n-1}), & F_{n-1}<k\le F_n. \end{cases} $$

Repeatedly applying this reduction eventually reaches $S_1$ or $S_2$. To make this explicit, write $k$ in Zeckendorf (Fibonacci) representation, i.e., as a sum of nonconsecutive Fibonacci numbers:

$$ k = F_{m_1}+F_{m_2}+\cdots+F_{m_r}, \quad m_1>m_2>\cdots>m_r\ge2, \quad m_i-m_{i+1}\ge2. $$

Then the $k$th letter is determined by the parity of the number of summands minus 1:

$$ w(k) = \begin{cases} a, & r \text{ even},\ b, & r \text{ odd}. \end{cases} $$

This gives a precise, nonrecursive criterion for the $k$th letter.

Example: $k=7=F_5+F_2=5+2$ has $r=2$ summands, so the 7th letter is $a$.

This rule completely resolves the $k$th-letter problem.

6. Density of b's

The proportion of $b$'s in $S_n$ is

$$ \frac{B_n}{|S_n|} = \frac{F_{n-2}}{F_n}. $$

Using Binet's formula

$$ F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt5},\quad \hat\phi=-\frac{1}{\phi}, $$

and noting $|\hat\phi|<1$, we find

$$ \lim_{n\to\infty}\frac{B_n}{|S_n|} = \phi^{-2} = 2-\phi. $$

Similarly, the density of $a$'s is

$$ \lim_{n\to\infty} \frac{A_n}{|S_n|} = \phi^{-1} = \phi-1. $$

These densities sum to 1, as expected.

7. Verification

Check $S_6 = \text{babbabab}$:

$$ A_6 = #\text{a's} = 3 = F_5,\quad B_6 = #\text{b's} = 5 = F_4 + F_3 = F_6 - F_5 = F_4 + F_3. $$

This agrees with the recursive definitions of $A_n$ and $B_n$ using Fibonacci indexing.

8. Summary of structural properties

  1. Length: $|S_n| = F_n$.
  2. Letter counts: $A_n=F_{n-1}$, $B_n=F_{n-2}$ for $n\ge2$.
  3. First letter: $\text{first}(S_n)=b$ for $n\ge2$.
  4. Last letter: Alternates: $\text{last}(S_n)=a$ if $n$ odd, $b$ if $n$ even.
  5. Double letters: No $aa$; $bb$ occurs at junctions $S_{n+2}=S_{n+1}S_n$ with $n$ odd and recursively at positions determined by Fibonacci sums.
  6. $k$th letter: Express $k$ in