Fibonacci word
= Fibonacci word
{c}
A word formed recursively by concatenating the previous two words in a specified order, for example $W_n=W_{n-2}W_{n-1}$ from two seed words. Lengths satisfy the <Fibonacci recurrence>. To locate a symbol, compare its index with the first block's length, choose the containing block, and subtract the first length when entering the second block. This avoids constructing an exponentially long word.