MathDB

A binary string is a sequence, each of whose terms is

0

1

. A set

\mathcal{B}

of binary strings is deﬁned 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}

.[/*]
For each positive integer

n

, let

b_n

be the number of binary strings in

\mathcal{B}

of length

n

.
[*]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).

B4