Combinatorics recursion question.

Question

How many binary vectors of length n do not contain a sequence '001' ? Solve by recursion and explain your solution.

Answer 1

Let $a_n$ and $b_n$ be the number of sequences not containing the sequece $001$ ending in $0$ and $1$, respectively. Given a desired sequence of length $n$, we can always add a $0$ at the end of it, so $$a_{n+1}=a_n+b_n$$ To get sequences ending in $1$ of length $n+1$, we can add $1$ to a sequence of length $n$ ending in $1$, or add $01$ to a sequence of length $n-1$, also ending in $1$. Hence $$b_{n+1}=b_n+b_{n-1}$$ As we have $a_1=1,a_2=2,b_1=1$ and $b_2=2$, $b_n=F_{n+1}$, where $F_n$ is the Fibonacci sequence, and $a_n$ can be calculated with the use of a telescopic sum to yield $$a_n=a_1+\sum_{k=1}^{n-1}b_k=a_1+\sum_{k=1}^nF_n-F_1=1+F_{n+2}-1-1=F_{n+2}-1,$$ where was used the property of the sum of the $n$ first Fibonacci numbers stated here. So, the number $x_n$ of sequences disered is $$x_n=a_n+b_n=F_{n+2}-1+F_{n+1}=F_{n+3}-1.$$ For an explicit form in terms of $n$, just check the link.