Find the number of binary sequences with a certain property.

Question

I'm looking for the formula giving $a_n=|\{b\in \{0,1\}^*:\#_0(b)+2\#_1(b)\leq n\}|$, where $\#_x(a)$ is the number of times that $x$ occurs in the sequence $a$. I noticed that if we rename 0 to 1 and 1 to 2 in the sequence, then we have a recurrence $a_n=a_{n-1}+P_{1,2}(n)$, where $P_{x,y}(n)$ is the number of different ways you can write $n$ as a sum of $x$'s and $y$'s, assuming we distinguish between $1+2$ and $2+1$. What else can I do?

Answer 1

After finding the first few values $a_0=1, a_1=2, a_2=4, a_3=7$, look in the OEIS. It is sequence A000071 with a different offset. Thus, $a_n=F_{n+3}-1$ with recursion $a_n=a_{n-1}+a_{n-2}+1$. This comes from looking at any sequence $b\in \{0,1\}^*$, where if it ends in $0$ the rest is counted by $a_{n-1}$, if it ends in $1$ the rest is counted by $a_{n-2}$, or else it is the empty sequence and counted once.