# Fibonacciwoord

De Fibonacciwoorden zijn woorden in een rij van opeenvolgende "woorden" of "strings" uit een binair alfabet van twee letters. Waar een Fibonaccigetal de som is van de twee voorgaande getallen in de rij van Fibonacci, is een Fibonacciwoord de concatenatie van de twee voorgaande Fibonacciwoorden.
Fibonacciwoorden zijn een bijzonder geval van Sturmiaanse woorden.

## Definitie

Stel dat het alfabet bestaat uit de "letters" 0 en 1. S$_n$ is het n-de Fibonacciwoord. Begin met S$_0$ = "0" en S$_1$ = "01". Voor n > 1 is dan:
S$_n$ = S$_{n−1}$S$_{n−2}$ (dus de concatenatie van het vorige en het voor-vorige Fibonacciwoord).
De opeenvolgende Fibonacciwoorden zijn dan:
* $S_{0}$ = 0
* $S_{1}$ = 01
* $S_{2}$ = 010
* $S_{3}$ = 01001
* $S_{4}$ = 01001010
* $S_{5}$ = 0100101001001
* $S_{6}$ = 010010100100101001010
* $S_{7}$ = 0100101001001010010100100101001001
Het (oneindig lange) Fibonacciwoord begint dus met: 010010100100101001010010010100100101001010010010100101....

## Substitutie of morfisme

Uit het n-de Fibonacciwoord kan men het n+1-de Fibonacciwoord bekomen door toepassing van een substitutie of morfisme:
* vervang de letter "1" door "0"
* vervang de letter "0" door "01"
Men kan dit schrijven als: $S_{n+1}=\sigma (S_{n})$ waarin $\sigma$ het morfisme is dat als volgt is gedefinieerd:
* $\sigma (1)=0$ en
* $\sigma (0)=01$
Het oneindige woord van Fibonacci is dan $S_{\infty }=\lim _{n\rightarrow \infty }\sigma ^{n}(1)$.

## Grafische constructie

Men kan het woord van Fibonacci ook bekomen door de opeenvolgende snijpunten van een rechte lijn met helling $\varphi$ of $\varphi -1$, met de horizontale en verticale lijnen van de gehele coördinaten (zie figuur hiernaast). $\varphi$ is het gulden getal. De snijpunten met de horizontale lijnen duidt men aan met "1" en die met de verticale lijnen met "0".

## Verband met Fibonaccigetallen

Er bestaat een nauw verband tussen de Fibonaccigetallen F$_n$ en de Fibonacciwoorden S$_n$. De lengte van het n-de Fibonacciwoord S$_n$ is gelijk aan het n-de Fibonaccigetal F$_n$. Het aantal "0" in het S$_n$ is gelijk aan F$_{n−1}$ en het aantal "1" is gelijk aan F$_{n−2}$.

## Diverse eigenschappen

* De n-de letter in het Fibonacciwoord is $2+\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor -\left\lfloor {\left({n+2}\right)\,\varphi }\right\rfloor$ waarin $\varphi$ het gulden getal is en $\left\lfloor x\right\rfloor$ de entier- of "floor"functie (n = 0,1,2...).
* Het oneindige Fibonacciwoord is niet periodiek. Het bevat nergens twee opeenvolgende "1" of drie opeenvolgende "0".
* De twee laatste letters van de Fibonacciwoorden zijn afwisselend "01" en "10".
* Het oneindige Fibonacciwoord bevat n+1 verschillende "subwoorden" van lengte n. Er zijn drie subwoorden van lengte 2: "01", "10" en "00"; vier subwoorden van lengte 3: "001", "010", "100" en "101" enz. Men zegt dat de complexiteitsfunctie van het oneindige Fibonacciwoord gelijk is aan n+1.
* Als men de twee laatste letters van een Fibonacciwoord weglaat houdt men een palindroom over.
* De verhouding tussen het totaal aantal letters en het aantal "0" in de Fibonacciwoorden S$_n$ neigt voor stijgende n naar $\phi$, het gulden getal.
* Het getal 0,010010100... waarvan de decimale fractie gevormd wordt door het oneindige woord van Fibonacci, is transcendent.

## Externe link

* Dr. Ron Knott, "The Fibonacci Rabbit sequence".
* ↑ rij A003849 in OEIS