How to simplify complicated Recursion.

If each term $a_k$ is either 0 or 1, how many sequences are there $a_1, a_2, \cdots$ , $a_n$ such that $$a_1 \leq a_2 \geq a_3 \leq a_4 \cdots?$$

If we let $f_n$ be the number of ways for a n-term sequence, we can get a recursive formula.

Suppose $a_1=1$. Then $a_2=1$ and $a_3=0,1$ which is actually $f_{n-2}$.

Suppose $a_1=0$. If $a_2=1$, we get $f_{n-2}$ by similar reasoning. If $a_2=0$, $a_3=0$ so the cycle repeats. Thus the # of ways in this case is $f_{n-2}+f_{n-4}+f_{n-6}+\cdots$.

So the recursive formula will be $$f_n=2f_{n-2}+f_{n-4}+f_{n-6}+\cdots$$ and $f_1=2, f_2=3$. How do I get a closed form, or did I find the wrong recursive relation?

For symmetry reasons, the number of $0/1$ sequences satisfying $$ \tag{1} a_1 \leq a_2 \geq a_3 \leq a_4 \ge \cdots a_n $$ and the number of $0/1$ sequences satisfying $$ \tag{2} a_1 \geq a_2 \leq a_3 \geq a_4 \le \cdots a_n $$ is the same. A sequence of type $(1)$ can be

• $1, 1,$ followed by another sequence of type $(1)$ with length $n-2$, or
• $0,$ followed a sequence of type $(2)$ with length $n-1$.

This leads to the recurrence relation $$ f_{n} = f_{n-1} + f_{n-2} $$ which happens to be the recurrence relation of the Fibonacci sequence $(F_n)$.

Finally note that $f_1 = 2 = F_3$ and $f_2 = 3 = F_4$.

Your recurrence, $$ f_{n}=2f_{n-2}+f_{n-4}+f_{n-6}+\dots\tag1 $$ is correct. You can make it a finite recurrence as follows. If you replace $n$ with $n-2$ in $(1)$, you get $$ f_{n-2}=2f_{n-4}+f_{n-6}+f_{n-8}+\dots\tag2 $$ Now, subtract equation $(2)$ from equation $(1)$.