How many sequences out of {0,1} in length n exists such that the sub-sequence 110 does not appear? I'm trying to solve the following simple problem:
How many sequences made of {0,1} and with length of n, exists such that the sub-sequence 110 does not appear?
Well, at first glance it looked to me as a simple recursion problem.
So I ended up with the following formula:
$ a_n=a_{n-1}+a_{n-2}+1 $
Which seems quite right to me.
But I think it is not sufficient, I need to provide an actual formula, and not a recursion. 
This formula is really similiar to the Fibonacci sequence, but how can I solve it? I am pretty disturbed by the 1 at the end, which does not let me solve it like a normal recursion.
Any suggestions? maybe it is possible without a recursion? 
Thanks in advance!
 A: To solve the recursion, just put $b_n=a_n+1$. Then $b_n=b_{n-1}+b_{n-2}$, which you know how to solve.
A: Let $a_n$ be the number of strings of length $n$ are there with no two ones in order and not ending in $1$?
If $n=0$ it is $1$. For $n=1$ it is $1$. Otherwise there are $a_{n+1}=a_n+a_{n-1}$ - either start such a string of length $n-1$ and add $10$ to the end, or take a such a string of length $n$ and add $0$ to the end.
Notice, this makes $a_n=F_{n+1}$ be the Fibonacci sequence.
Now, if $b_n$ is the number of strings of your sort (no 110), then it must be an $a_k$ for some $0\leq k\leq n$ plus a string of $n-k$ $1$s. So:
$$b_n=a_0+a_1+\cdots+a_n$$
If you know your Fibonacci sequences, you can get a closed for for $b_n$ in terms of the Fibonacci sequence, namely $b_n=F_{n+3}-1$.
A: Typically, one solves a "linear, non-homogeneous, difference equation" by first finding the general solution to the associated homogeneous equation, then adding a specific solution to the entire equation.  The "associated homogeneous equation" here is $a_n= a_{n-1}+ a_{n-2}= 0$.  We look for a solution of the form $a_n= x^n$ for some constant, x. Then $a_{n-1}= x^{n-1}$ and $a_{n-2}= x^{n-2}$.  Putting that into the homogeneous equation, $x^n= x^{n-1}+ x^{n-2}$ or $x^n- x^{n-1}- x^{n-2}= 0$.  Factoring $x^{n-2}$ gives $x^{n-2}(x^2- x- 1)= 0$.  x= 0 gives the trivial solution, $a_n= 0$ for all n.  If x is not 0 then we must have $x^2- x- 1= 0$ which is equivalent to $x^2- x= x^2- x+ \frac{1}{4}= (x+ \frac{1}{2})^2= 1+ \frac{1}{4}= \frac{5}{4}$.  That is, $x+ \frac{1}{2}= \pm\frac{\sqrt{5}}{2}$.  The general solution to the associated homogeneous equation is $a_n= C(1+\sqrt{5}/2)^n+ D(1- \sqrt{5}/2)^n$.
Now, since the non-homogenous part is simply the constant "1", I would try a constant solution to the entire equation: $a_n= A$ where A is a constant.  Then $a_n- a_{n-1}- a_{n-2}= A- A- A= -A= 1$ so A= -1.  The general solution to the entire equation is $a_n= C(1+\sqrt{5}/2)^n+ D(1- \sqrt{5}/2)^n- 1$
A: Solving the recursion is straightforward, discovering the recursion was far from obvious for me.
My long winded approach was to create a DFA that accepts any string containing $110$ and count the number of times a string ends up in a
non accepting state.
Here is a suitable DFA: 

We are interested in counting strings that leave the DFA in the $s,t,u$ states.
Let $s_n$ represent the number of length $n$ strings that end up in the $s$ state, and similarly for $t_n,u_n$. Note that
$s_0 = 1, t_0 = 0, u_0 = 0$, and 
$a_n = s_n+t_n+u_n$.
From the DFA we get the equations
\begin{eqnarray}
s_{n+1} &=& s_n+t_n \\
t_{n+1} &=& s_n \\
u_{n+1} &=& u_n+t_n \\
\end{eqnarray}
Letting $z_n=(s_n,t_n,u_n)^T$, $A=\begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1  & 1\end{bmatrix}$, the equations becomes
$z_{n+1} = Az_n$ with solution $z_n = A^n z_0$ and $z_0 = (1,0,0)^T$. The eigenvalues
are $\lambda_1=1$, $\lambda_2={1 \over 2} (1 - \sqrt{5})$, $\lambda_3 = {1 \over 2} (1 + \sqrt{5})$ hence $A$ is diagonalisable and we
can compute a formula for $z_n$ if necessary.
To derive the formula in the question, let $e= (1,1,1)^T$ and note that
$a_n = s_n+t_n+u_n = e^T A z_n$, and so
$a_{n+2}-a_{n+1}-a_n = e^T(A^2-A-I) A^n z_0$. We find that
$e^T(A^2-A-I) = (1, 0,-1)^T$ and $(1, 0,-1)^T = (1, 0,-1)^TA $
and so $a_{n+2}-a_{n+1}-a_n = (1, 0,-1)^T z_0 = 1$.
Note that $a_0 = 1, a_1 = 2$.
To solve the recurrence, we note that there is a particular
solution $n \mapsto -1$, and since $x^2-x-1 = 0$ has roots
$\lambda_2, \lambda_3$, the solution is given by
$a_n = \alpha \lambda_2^n + \beta \lambda_3^n -1$ where
$\alpha,\beta$ are chosen to satisfy the initial conditions
$a_0 = 1, a_1 = 2$. Grinding through gives
$\alpha = 1-{2 \over \sqrt{5}}, \beta = 1+{2 \over \sqrt{5}}$ and
so the solution is
$$a_n = (1-{2 \over \sqrt{5}}) ({1 - \sqrt{5} \over 2})^n + (1+{2 \over \sqrt{5}}) ({1 + \sqrt{5} \over 2})^n -1$$
(While the original equation was not explicit, I suspect that it is
far more identifiable as a recursion than as an explicit formula!)
