# Binary sequences with even places not less than immediate neighbors [duplicate]

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.

• @cosmo5 did it, thanks Oct 27, 2020 at 20:52
• There are only two possible symbols $0$ and $1$. Why is $3$ there? Oct 27, 2020 at 21:01
• @cosmo5 based on the <= or >=, that would be different :-?? I mean for example, x1=0, then x2 could be 0 or 1, then x3 has to be less equal x2, so x3 could be 0 if x2 =0, and it could be 1 if x2=0 or x2=1, so 3 possibilities :-?? Oct 27, 2020 at 21:02

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$$.

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).