Let $a_n$ be the position of the nth $1$in the string $t_n$. Prove that: $a_n = [\frac{1+\sqrt5}{2} . n]$

Consider the transformation $f$ acting on a binary string: turn every $(0, 1)$ in it into$ (1, 01).$ The notation$ s_n$ is the string produced after acting$ f $on $1$ all n times. Example :$ 1\Rightarrow 01 \Rightarrow 101 \Rightarrow 01101 \Rightarrow ...$

$1)$ Calculate the number of pairs$ (0,0) $appearing in the string $s_n$

$2)$ Arrange consecutive strings $s_1, s_2,... s_n$ into a string $t_n$ . Let $a_n$ be the position of the nth $1$ and $b_n$ the position of the nth $0$ in the string $t_n$ . Prove that:

$a_n = [\frac{1+\sqrt5}{2} . n]$ , $b_n = [\frac{1+3\sqrt5}{2} . n]$ Note: $[z]$ is the floor function.

$+)$We will prove inductively that no two zeros are next to each other $.(1)$

Let $(1)$ be true for $n = k .$ Consider the following minor cases:

Case $1: ....11.... \Rightarrow ....0101....$

Case $2: 01... \Rightarrow 101.....$

Case $3: 101....\Rightarrow 01101....$

So $(1)$ is also true for $n = k+1 .$ We complete the proof $(1).$

Thus the number of pairs $(0,0)$ in the string $s_n = 0$ for all $n.$

I am very stuck with request $2) . $I hope to get help from everyone. Thanks very much !

Solution 1:

Hint: we can see something related to Fibonacci, especially, we can see that $S_{k+2} = \operatorname{Concatenate}(S_{k}, S_{k+1})$, for $k \geq 1$