# Problem 29: Strict Border Table of the Fibonacci Word

$$\def\tbord{\mathit{border}} \def\sbord{\mathit{stbord}} \def\tper{\mathit{period}} \def\dd{\dot{}\dot{}} \def\sa#1{\tt{#1}}$$

The border table $\tbord$ (see Problem 19) of the infinite Fibonacci word $\mathbf{f}$ has a simple structure but values in its strict border table $\sbord$ (see Problem 25) look chaotic at first glance. The problem examines a simple relation between the two tables, which helps to quickly compute any individual value of the table $\sbord$.

Below are the tables of periods, borders and strict borders related to a prefix of the Fibonacci word. Values at index $\ell$ correspond to the prefix $\mathbf{f}[0\dd \ell-1]$ of length $\ell$.
 $i$ 0 1 2 3 4 5 6 7 8 9 10 $x[i]$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\ell$ 0 1 2 3 4 5 6 7 8 9 10 11 $\tper[\ell]$ 1 2 2 3 3 3 5 5 5 5 5 $\tbord[\ell]$ -1 0 0 1 1 2 3 2 3 4 5 6 $\sbord[\ell]$ -1 0 -1 1 0 -1 3 -1 1 0 -1 6

Show how to compute in logarithmic time the $n$th element of the strict border table of the infinite Fibonacci word $\mathbf{f}$.
Examine positions where tables $\tbord$ and $\sbord$ match.