Fraction of length-$n$ binary numbers satisfying a constraint Problem:  Derive an expression for the fraction of length-$n$ binary numbers that do not contain the subsequence $010$.  
Background:  The total number of $n$-bit binary numbers is of course $2^n$.  Some of these numbers have the sequence $010$ within it; others do not.  In short, the problem is to determine, for a given $n$:
${{\rm number\ of\ sequences\ without\ 010} \over 2^n}$.
Although it is a simple matter to determine this fraction through simulation and curve fitting, it is rather tricky to determine the fraction through combinatorics or other rigorous means.
Clearly for $n=3$, there are $2^3 = 8$ possible binary numbers of length $3$ and only one of them is $010$.  Thus for $n=3$, the fraction is:
${7 \over 8}$.
Background reading:  Binary strings without zigzags and a related question.
 A: The sequence is given in OEIS A005251 with a recurrence $a(n)=a(n-1)+a(n-2)+a(n-4)$ and begins $1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405, 97229, 170625, 299426, 525456, 922111, 1618192, 2839729, 4983377, 8745217, 15346786, 26931732, 47261895, 82938844, 145547525$  It grows about as $1.7549^n$ so the fraction is about $0.8774^n$
A: Let $a_n$ be the number of admissible sequences ending in $0$, let $b_n$ be the number of admissible sequences ending in $01$, and let $c_n$ be the number of admissible sequences ending in $11$. Then
\begin{align}
a_{n+1}&=a_n+c_n\;,\\
b_{n+1}&=a_n\;,\\
c_{n+1}&=b_n+c_n\;,
\end{align}
or
$$
\pmatrix{a\\b\\c}_{n+1}=\pmatrix{1&0&1\\1&0&0\\0&1&1}\pmatrix{a\\b\\c}_n\;.
$$
Then with $d_n=a_n+b_n+c_n$ the total number of admissible sequences, we have
\begin{align}
d_{n+1}&=d_n+a_n+c_n\\
&=d_n+a_{n-1}+c_{n-1}+b_{n-1}+c_{n-1}\\
&=d_n+d_{n-1}+c_{n-1}\\
&=d_n+d_{n-1}+b_{n-2}+c_{n-2}\\
&=d_n+d_{n-1}+a_{n-3}+b_{n-3}+c_{n-3}\\
&=d_n+d_{n-1}+d_{n-3}\;,
\end{align}
the recurrence that Ross quoted from OEIS. The growth rate is then obtained as the solution of the characteristic equation
$$
\lambda^4-\lambda^3-\lambda^2-1=0
$$
with highest magnitude. The solution $\lambda=-1$ can be guessed, and the factored equation
$$
(\lambda^3-2\lambda^2+\lambda-1)(\lambda+1)=0
$$
has, according to Wolfram|Alpha, the real solution
$$
\lambda=\frac16\left(4+\sqrt[3]{100-12\sqrt{69}}+\sqrt[3]{100+12\sqrt{69}}\right)\approx1.7549\;.
$$
A: I upvoted the answer by @Joriki which is exemplary.
This can also be done using generating functions.
We get
$$G(z) = \frac{1}{1-z} + \frac{1}{1-z} \frac{z}{1-z} 
\sum_{q\ge 0} \left(\frac{z^2}{1-z}\frac{z}{1-z}\right)^q
\frac{1}{1-z}.$$
Explanation: first term  a string of ones.  Remaining term: admissible
sequences containing at least one zero. This is
$$1^* 0^+ (11^+ 0^+)^* 1^*.$$
We thus obtain
$$G(z) = \frac{1}{1-z}
+ \frac{z}{(1-z)^3} \frac{1}{1-z^3/(1-z)^2}
= \frac{1}{1-z}
+ \frac{z}{1-z} \frac{1}{1-2z+z^2-z^3}
\\ = \frac{z+1-2z+z^2-z^3}{1-z} \frac{1}{1-2z+z^2-z^3}
= \frac{1-z+z^2-z^3}{1-z} \frac{1}{1-2z+z^2-z^3}
\\ = \frac{1+z^2}{1-2z+z^2-z^3}.$$
Now the dominant contribution  (the asymptotical factor being sought)
emerges from the inverses of the poles, i.e. the roots of
$$z^3(1-2/z+1/z^2+1/z^3) = z^3-2z^2+z-1.$$
Using a computer algebra system we find the dominant root to be
$$1.754877667$$
and the rest continues as before.

The dominant contribution emerges from  the inverses because the poles
are all simple and hence we have
$$\frac{1+z^2}{1-2z+z^2-z^3}
= \sum_{1-2\rho+\rho^2-\rho^3 = 0}
 \frac{1}{z-\rho} \mathrm{Res}_{z=\rho} \frac{1+z^2}{1-2z+z^2-z^3}$$
and
$$\frac{1}{z-\rho} = - \frac{1}{\rho} \frac{1}{1-z/\rho}.$$
