|
| Fibonacci |
| We onderwerpen het rijtje 0, 1, 10, 101, 10110, 10110101, ... aan een nadere inspectie. Merk op, dat als we in elke term van dit rijtje de laatste 2 bits afhalen (vanaf term 3), er een rijtje van palindromen ontstaat, n.l. 1, 101, 101101, 10110101101, ... In de termen van het rijtje komen nooit 2 nullen of 3 enen na elkaar voor. Hoeveel verschillende patronen van opeenvolgende nullen en enen van lengte k kun je ontdekken in de termen van het rijtje? Voor lengte k is dan k+1, b.v. van lengte 1 is dat {0,1}, van lengte 2 {10,11,01}, van lengte 3 {010,110,101,011}, van lengte 4 {0101,0110,1010,1101,1011}, enz. Merk op: Het aantal patronen van lengte k+1 is één groter dan het aantal patronen van lengte k. Dat houdt in dat we achter elk van de patronen van lengte k, op een na, precies 1 nul of 1 één kunnen plaatsen, en achter precies één van die patronen zowel een 1 als een 0 kunnen plaatsen om alle patronen van lengte k+1 te krijgen. Als we die patronen waarachter we zowel een 1 als een 0 kunnen plaatsen opsommen krijgen we: 1,01,101,1101,01101,101101,... Lees de termen achterstevoren om de relatie met het oorspronkelijke rijtje te ontdekken. Elk term van het oorspronkelijke rijtje ontstaat uit de voorafgaande term door daar elke 0 te vervangen door een 1 en elke 1 door 10. Een variant is, elke 0 door 01 vervangen en elke 1 door 10. Dat geeft het rijtje van Thue-Morse.
|