Linear Homogenous Recurrences "What is the number of binary sequences of length n with no "100" "

Question

So I have a word problem I am stuck on. I have studied linear Homogeneous and non-homogeneous recurrences fairly in depth as I have to present my findings and teach it to my senior thesis class.
the question is;

"What is the number of binary sequences of length n with no "100" ? "

so I know

The EQ (equation) for linear recurrences is

$a_n$=$c_1A_{n-1}+c_2A_{n-2}+...+c_kA_{n-k}+f(n)$

where in a homogeneous the f(n)=o

then you can use the characteristic EQ $r{^k}-c{^1}A{^{n-1}}+c{^2}A{^{n-2}}+...+c{^k}A{^{n-k}}$

so then you can find the roots and find your finished answer.(a very brief overview) so, I am confused on how this word problem fits into this...

can someone point me in the right direction ??

the other word problem I am stumped on is

"What is the number of binary sequences of length n with no consecutive 00's?"

Answer 1

A binary sequence with no "00" can have its last bit 0 or 1.

Let $a_n$ and $b_n$ be the number of n-bit binary numbers with no 00 ending with, respectively 0 or 1.

Figure out the recurrence for $a_{n+1}$ and $b_{n+1}$ in terms of $a_n$ and $b_n$.

What you want is $a_n+b_n$.

If you are lucky, the recurrences will give you a recurrence for $a_{n+1}+b_{n+1}$ in terms of $a_n+b_n$.

If not, you will have to solve the individual recurrences.

Have at it.

Answer 2

So you are looking for the strings that do not contain consecutive $0$'s.
Such strings start either with $0$ or with $1$.
Call $N_1(n)$ the number of those starting with $1$. Then those starting with $0$ shall clearly be $N_0(n)=N_1(n-1)$.
Also, those starting with $1$ will then continue with a $1$ or a $0$.

That is $$ \left\{ \matrix{ N(n) = N_{\,1} (n) + N_{\,0} (n) \hfill \cr N_{\,0} (n) = N_{\,1} (n - 1) \hfill \cr N_{\,1} (n) = N(n - 1) = N_{\,1} (n - 1) + N_{\,0} (n - 1) \hfill \cr} \right. $$ or $$ \left\{ \matrix{ N(n) = N_{\,1} (n) + N_{\,0} (n) = N_{\,1} (n) + N_{\,1} (n - 1) \hfill \cr N(n) = N_{\,1} (n + 1) \hfill \cr} \right. $$ and finally $$ N_{\,1} (n + 1) = N_{\,1} (n) + N_{\,1} (n - 1)\quad \left| \matrix{ \;N_{\,1} (0) = 0 \hfill \cr \;N_{\,1} (1) = 1\; \hfill \cr} \right. $$

You will recognize here a famous recursion.