Exercise 3.4.9 of The Dragon Book defines Fibonacci strings as follows:

  1. $s_1 = b$.
  2. $s_2 = a$.
  3. $s_k = s_{k-1}s_{k-2}$ for $k>2$.

Part (d) then poses the following question:

Show that the failure function of $s_n$ can be expressed by $f(1) = f(2) = 0$, and for $2 < j \le |s_n|$, $f(j)$ is $j - |s_{k-1}|$ where $k$ is the largest integer such that $|s_k| \le j + 1$.

For avoidance of doubt, the failure function $f$ of a string $b_1b_2\ldots{}b_n$ is defined for integer values $i$ satisfying $1 \le i \le n$ in order that $b_1b_2\ldots{}b_{f(i)}$ is the longest proper prefix of $b_1b_2\ldots{}b_i$ that is also a suffix of the latter. Thus $f(i)$ is the length of the longest proper prefix of $b_1b_2\ldots{}b_i$ that is a suffix of $b_1b_2\ldots{}b_i$ also.

I have struggled for a long time and cannot see how to solve this question: can anyone explain this? I can see that the failure function of $s_{n-1}$ will be identical with that of $s_n$ until $j > |s_{n-1}|$ but beyond this I have not managed.

  • 1
    $\begingroup$ I'm not sure if it's the easiest way forward, but you can use the fact that the infinite fibonacci word has exactly $n+1$ distinct factors of length $n$. This helps to show that for $j=|s_k|$ then $f(j) = |s_{k-2}| = j- |s_{k-1}|$ since $s_k = s_{k-1}s_{k-2} = s_{k-2}s_{k-3}s_{k-2}$ so $s_{k-2}$ is the failure string. Now if you show all factors of size $|s_{k-2}| + 1$ are distinct, there is no longer failure string. $\endgroup$
    – Janmar
    Commented Aug 25, 2022 at 9:35
  • $\begingroup$ I'm not sure exactly what you mean in the final sentence—how does it help to know that there is no longer any failure string? $\endgroup$
    – akiarie
    Commented Aug 26, 2022 at 14:08
  • $\begingroup$ It was only a direction, but the point is that formatting $s_k = s_{k-2}s_{k-3}s_{k-2}$ shows there is failure string of size $|s_{k-2}|$, hence $f(k)\geq |s_{k-2}|$. But in order to be sure that $f(k) = |s_{k-2}|$ you need to confirm there is no longer failure string. $\endgroup$
    – Janmar
    Commented Aug 29, 2022 at 9:16

1 Answer 1


It is easy to use straightforward induction to prove the following two claims.

Claim One: $s_n$ starts with $s_k$ for $2\le k\le n$. In particular, $s_n$ starts with $ab$ for $n\ge3$.

Claim Two: $s_k$ ends with either $ab$ when $k$ is odd or $ba$ when $k$ is even for $k\ge3$.

Claim Three: $s_ks_{k-1}$ and $s_{k-1}s_k$ are the same except the last two letters, which are either $ab$ or $ba$ for $k\ge2$.

Proof: For $k=2$, $s_2s_1=ab$ and $s_1s_2=ba$ are the same except the last two letters, which are either $ab$ or $ba$.

Suppose $k\ge3$.
Thanks to induction hypothesis that says $s_{k-2}s_{k-1}$ and $s_{k-1}s_{k-2}$ are the same except the last two letters, which are either $ab$ and $ba$, so are $s_ks_{k-1}$ and $s_{k-1}s_k$.

Claim Four: Let $f$ be the failure function of $s_n$, $n\ge3$. Then $f(1)=f(2)=0$ and for $2\lt|s_k|-1\le j\le \min(|s_n|, |s_{k+1}|-2)$, we have $f(j)=j-|s_{k-1}|$.

Note that Claim Four is Exercise 3.4.9 stated in a slightly different way.

Proof: WLOG, suppose $n$ is large enough, thanks to Claim One.
$f(1)=0$ by definition.
Since $s_n$ starts with $ab$, $f(2)=0$.

Let $w[i]$ mean the $i$-th letter of string $w$, i.e., $w$ is the sequence $w[1]$, $w[2]$, $\cdots$, $w[\text{length of }w]$.

Let $1\le x\le |s_{k+1}|-|s_{k-1}|=|s_{k-1}| + |s_{k-2}|$.
Since $s_n = s_k\cdots =s_{k-1}s_{k-2}\cdots$, we have $s_n[x] = (s_{k-1}s_{k-2})[x]$.
Since $s_n= s_{k+1}\cdots = s_ks_{k-1}\cdots=(s_{k-1}s_{k-2})s_{k-1}\cdots=s_{k-1}(s_{k-2}s_{k-1})\cdots$, we have $s_n[|s_{k-1}|+x]=(s_{k-2}s_{k-1})[x]$.

Thanks to Claim Three, we have $s_n[x] = s_n[|s_{k-1}|+x]$ if $x\le|s_{k-1}| + |s_{k-2}|-2$, which implies $f(j)\ge j-|s_{k-1}|$ for $|s_k|-1\le j\le |s_{k+1}|-2$.

Now we can apply the standard algorithm that builds this failure function $f$ of KMP algorithm, where the base cases are easy and the length of match $f(j)$ always increases by $1$ when $j$ increases by $1$, unless at the time when $j$ increases to $|s_{k+1}|-1$ for some $k$, as shown above.

At that time when $j$ increases to $|s_{k+1}|-1$, $f(\cdot)$ does not increase by $1$ since $$\begin{aligned} s_n[j-|s_{k-1}|]&=(s_{k-1}s_{k-2})[j-|s_{k-1}|]\\ &\not=(s_{k-2}s_{k-1})[j-|s_{k-1}|]\\ &= s_n[(j-|s_{k-1}|)+ |s_{k-1}|]\\ &=s_n[j], \end{aligned}$$ where the inequality comes from Claim Two as $j-|s_{k-1}|=|s_{k-2}s_{k-1}|-1$.

Hence, by the nature of the failing function, the most $f(j)$ could be is $f(f(j-1))+1$. Thanks to the induction hypothesis, $$f(f(j-1))+1=f(|s_k|-2|)+1= |s_{k-1}|-1=j-|s_k|.$$ Since $|s_{k+1}|-1\le j\le |s_{k+2}|-2$, we have proved above that $f(j)\ge j-|s_k|$. Hence $f(j)=|s_{k-1}|-1=j-|s_{k}|$ as wanted. $\quad\checkmark$.

  • $\begingroup$ Studying this to understand it, but it is very illuminating. Thank you for putting in the time to explain it so clearly. $\endgroup$
    – akiarie
    Commented Aug 26, 2022 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.