The Fibonacci word fractal defines a sequence of bitstrings using a similar recursive description to the Fibonacci numbers. Here’s the definition: For example, we have s3 = s2 ◦ s1 = 01 and s4 = s3 ◦...

The Fibonacci word fractal defines a sequence of bitstrings using a similar recursive description to the Fibonacci numbers. Here’s the definition:

For example, we have s3 = s2 ◦ s1 = 01 and s4 = s3 ◦ s2 = 010 and s5 = s4 ◦ s3 = 01001 and s6 = s5 ◦ s4 = 01001010. It turns out that if we delete the last two bits from sn, the resulting string is a palindrome (reading the same back-tofront and front-to-back). Here you’ll prove a few slightly simpler properties, using strong induction on n

1.The number of bits in sn is precisely fn (the nth Fibonacci number).

2. The string sn does not contain two consecutive 1s or three consecutive 0s.

3. Let #0(x) and #1(x) denote the number of 0s and 1s in a bitstring x, respectively. Show that, for all n ≥ 3, the quantity #0(sn) − #1(sn) is a Fibonacci numbe