How many sequences out of {0,1} in length n exists such that the sub-sequence 110 does not appear?

Question

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!

Answer 1

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.

Answer 2

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$.

Answer 3

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$

Answer 4

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!)