# Failure function of the Fibonacci strings (The Dragon Book Exercise 3.4.9d)

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.

• 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. Commented Aug 25, 2022 at 9:35
• 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? Commented Aug 26, 2022 at 14:08
• 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. Commented Aug 29, 2022 at 9:16

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$$.
$$s_ks_{k-1}=(s_{k-1}s_{k-2})s_{k-1}=s_{k-1}(s_{k-2}s_{k-1}).$$
$$s_{k-1}s_k=s_{k-1}(s_{k-1}s_{k-2})$$
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$$.

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