Binary sequences with even places not less than immediate neighbors

Question

How many $n$-length binary sequences, $(x_1,x_2,\ldots x_n)$, are there such that $x_1 ≤ x_2 ≥ x_3 ≤ x_4 ≥ x_5 \le \ldots$ ?

My attempt but I am not sure it is correct (finding pattern): My attempt

How to find out the solution to this problem? Any hint/reference would be also appreciated.

Thanks in advance.

Answer 1

HINT: A good start would be to list the acceptable $n$-bit sequences for $n=1,2,3,4$:

$$\begin{array}{c|c} n&\text{sequences}\\\hline 0&\text{empty sequence}\\ 1&0\quad 1\\ 2&00\quad 01\quad \color{red}{11}\\ 3&000\quad 010\quad 011\quad \color{red}{110\quad 111}\\ 4&0000\quad 0001\quad 0100\quad 0101\quad 0111\quad \color{red}{1100\quad 1101\quad 1111} \end{array}$$

If $a_n$ is the number of acceptable $n$-bit sequences, we now know that $a_0=1$, $a_1=2$, $a_2=3$, $a_3=5$, and $a_4=8$. The sequence $1,2,3,5,8$ should be recognizable as the Fibonacci numbers $F_2,F_3,F_4,F_5$, and $F_6$; this suggests the conjecture that $a_n=F_{n+2}$. One way to prove this would be to show that $a_n=a_{n-1}+a_{n-2}$ for $n\ge 2$.

I’ve added color to the table to suggest how this might be done: the coloring suggests that there might in general be $a_{n-1}$ acceptable $n$-bit sequences that start with $0$ and $a_{n-2}$ that start with $11$. The latter conjecture is quite easy to prove. The former is a little trickier: you have to recognize and prove that $b_1\ldots b_{n-1}$ is an acceptable $(n-1)$-bit sequence if and only if $0\bar b_1\ldots\bar b_{n-1}$ is an acceptable $n$-bit sequence, where $\bar 0=1$ and $\bar 1=0$.

Answer 2

Hint: Consider this problem in cases!

Define $f(n)$ to be the number of binary sequences of length $n$.
Define $f_1(n)$ to be the number of binary sequences of length $n$ beginning with $1$.
Define $f_0(n)$ to be the number of binary sequences of length $n$ beginning with $0$.

C1: We begin with $x_1=1$, $x_2=1$
If that's the case, then the number of combinations is given by $f(n-2)$ ($x_3$ can be either $1$ or $0$ and $x_3 \leq x_4$, so the conditions mirror the relationship between $x_1$ and $x_2$)

C2: $x_1=1$, $x_2=0$
This is impossible because the rules says that $x_1 \leq x_2$

Therefore, $f_1(n) = f(n-2)$

C3: $x_1=0$, $x_2=1$
The number of combinations is given by $f(n-2)$ (for the same reasons as C1)

C4: $x_1=0$, $x_2=0$
The number of combinations is given by $f_0(n-2)$ ($x_3$ has to be $0$, so it's not the same as C1 or C3)

Therefore, $f_0(n) = f(n-2) + f_0(n-2)$

Putting it all together: $$f(n) = f_1(n) + f_0(n) = 2f(n-2) + f_0(n-2)$$ $$= 2(2f(n-4) + f_0(n-4)) + (f(n-4) + f_0(n-4)) = 5f(n-4) + 3f_0(n-4)$$ $$= 5(2f(n-6) + f_0(n-6)) + 3(f(n-6) + f_0(n-6)) = 13f(n-6) + 8f_0(n-6)$$ $$...$$

There's a pattern to the coefficients! Find that pattern (maybe look at Brian M. Scott's hint!) and express f(n) in terms of something you know like f(2), which we showed to be 3 (the coefficients will be in terms of n).