SIMON-MARAIS 2019 B4

A binary string is a sequence, each of whose terms is $0$ or $1$ . A set $\mathcal{B}$ of binary strings is defined inductively according to the following rules.

• The binary string $1$ is in $\mathcal{B}$ .[/*]
• If $s_1,s_2,\dotsc ,s_n$ is in $\mathcal{B}$ with $n$ odd, then both $s_1,s_2,\dotsc ,s_n,0$ and $0,s_1,s_2,\dotsc ,s_n$ are in $\mathcal{B}$ .[/*]
• If $s_1,s_2,\dotsc ,s_n$ is in $\mathcal{B}$ with $n$ even, then both $s_1,s_2,\dotsc ,s_n,1$ and $1,s_1,s_2,\dotsc ,s_n$ are in $\mathcal{B}$ .[/*]
• No other binary strings are in $\mathcal{B}$ .[/*] [/list] For each positive integer $n$ , let $b_n$ be the number of binary strings in $\mathcal{B}$ of length $n$ . [list=a]
• Prove that there exist constants $c_1,c_2>0$ and $1.6<\lambda_1,\lambda_2<1.9$ such that $c_1\lambda_1^n<b_n<c_2\lambda_2^n$ for all positive integer $n$ .[/*]
• Determine $\liminf_{n\to \infty} {\sqrt[n]{b_n}}$ and $\limsup_{n\to \infty} {\sqrt[n]{b_n}}$ [/*]

Note: The problem is open in the sense that no solution is currently known to part (b).