Binary sequences with even places not less than immediate neighbors 
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.
 A: 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$.
A: 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).
