Call a sequence of length $n$ good if it has no two consecutive $0$ (no other restriction).
Let $g_n$ be the number of good sequences of length $n$.
Now look at our more restricted collection, with the added condition that if we start with $0$ we must end with $1$. There are two types of such sequences of length $n$.
(i) The sequences of length $n$ that start with $1$. We can get these by taking any good sequence of length $n-1$, and putting a $1$ in front. There are therefore $g_{n-1}$ of these.
(ii) The sequences of length $n$ that start with $0$. Then the next entry must be $1$, and the last must be $1$. In between can be any good sequence of length $n-3$, so there are $g_{n-3}$ of these.
So if $a_n$ is the number of restricted condition sequences of length $n$, then
$$a_n=g_{n-1}+g_{n-3}.$$
Now we go after the $g_n$, a more familiar problem. It turns out that the $g_n$ are just the Fibonacci numbers. For a good sequence of length $n$ either ends with a $1$ or a $0$. If it ends with $1$, it can be produced by appending a $1$ to a good sequence of length $n-1$. If it ends with $0$, then the previous entry (if any) must be $1$, and the part before that is any good sequence of length $n-2$. Thus $g_n=g_{n-1}+g_{n-2}$.
Now put the pieces together. Note that $g_0=1$ and $g_1=2$.
Well , generally the best method for finding recurrence relation is Goulden-Jackson -Cluster Method. It is very powerful tool to find any recurrence relations. (I want to especially thank to @Markus Scheuer for this beautiful method)
I am putting a link for you : https://arxiv.org/abs/math/9806036 ,you can learn more about it.
Now , i will get in the solution to show you another method.
According to the article , our bad words are $000,111$.
Then , our alphabet is $V= \{0,1\}$
$$A(x)= \frac{1}{1-dx-weight(C)}$$ with $d=|V|=2$ and $weight(C) = weight(C[000])+ weight(C[111])$
Lets calculate $weight(C[000])$ according to the paper such that
$weight(C[000])= -x^3 - (x +x^2)weight(C[000])$
So , $weight(C[000]) = \frac{-x^3}{(1+x +x^2)} $
Lets calculate $weight(C[111])$ according to the paper such that
$weight(C[111])= -x^3 - (x +x^2)weight(C[111])$
So , $weight(C[111]) = \frac{-x^3}{(1+x +x^2)} $
Then , we said that $weight(C) = weight(C[000])+ weight(C[111])$ .Hence , $$weight(C) = \frac{-2x^3}{1+x+x^2} $$
Then , $$A(x) = \frac{1}{1-2x -\frac{-2x^3}{1+x+x^2}} = \frac{1+x+x^2}{1-x-x^2}$$
Now , we will turn this fraction into recurrence relation. See for instance theorem 4.1.1 in Enumerative Combinatorics, Vol. I by R. P. Stanley. (https://www.maa.org/press/maa-reviews/enumerative-combinatorics-vol-i)
According to the book , $$\frac{1+x+x^2}{1-x-x^2}= a_n= a_{n-1} + a_{n-2}$$
Moreover , $$\frac{1+x+x^2}{1-x-x^2}=1+2x+4x^2 +6x^3 + \color{blue}{10x^4} + 16x^5+...$$
This sequence says that there are $10$ binary strings of lenght $4$ that do not contain $3$ zeros or $3$ ones.
You can see the sequence by exapnding wolfram-alpha such that https://www.wolframalpha.com/input/?i=expanded+form+of+%281%2Bx%2Bx%5E2%29%2F%281-x-x%5E2%29
When we come to neither $k$ zeros nor $k$ ones. The system turned out to be
$$A(x) = \frac{1}{1-2x - \frac{-2x^k}{1+x+x^2 +...+x^{k-1}}}$$
where
$weight(C[000])= -x^k - (x +x^2+..+x^{k-1})weight(C[000])$
$weight(C[111])= -x^k - (x +x^2+..+x^{k-1})weight(C[111])$
So , $$A(x) = \frac{1+x+x^2+..x^{k-1}}{1-x-x^2 - ...-x^{k-1}}$$
Then , by the same method ; $$a_{n+k-1}-a_{n+k-2}-a_{n+k-3}-...-a_{k-1}=0$$
Then , for example , if $k=5$ , then $$a_{n+4}-a_{n+3}-a_{n+2}-...-a_{n}=0$$
So , $$a_n=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}$$
As a result , for any $k >1 $ ,the number of binary strings that do contain neither $k$ zeros nor $k$ ones is : $$a_n=a_{n-1}+a_{n-2}+...+a_{n-k+1}$$
Best Answer
First let's consider the related question: how many subsets $A \subseteq \{1,\dots,n\}$ are there such $A$ does not contain two consecutive elements? Denote this number by $g(n)$. If $A$ contains 1, then $A$ cannot contain $2$ and $A \setminus \{1\}$ is a subset of $\{3,\dots,n\}$ not containing any consecutive elements. This gives us $g(n-2)$ possibilities. If $A$ does not contain 1, then $A$ is a subset of $\{2,\dots,n\}$ not containing any consecutive elements, so there $g(n-1)$ possibilities. Hence, $g(n) = g(n-2) + g(n-1)$. Note that $g(1) = 2$ and $g(2) = 3$. This implies that $g(n)$ is the $(n+2)$th Fibonnaci number (with the convention that the first two Fibonacci numbers are 1). Let's denote the $n$th Fibonacci number by $\mathcal F_n$.
Now, let's look at the friendly sequences of length $n$. A sequence $S$ is friendy iff the set $A$ of positions where $S$ equals $0$ does not contain $2$ or $n-1$, and $A$ does not contain two numbers at distance $2$ from each other. So we can look at the odd and even positions separately. Define the following sets.
If $n$ is even, then $A_1$ and $A_2$ must be subsets without consecutive elements of $\{ 1,\dots,\frac n 2 -1\}$ and $\{2,\dots,\frac n 2\}$ respectively. Note that we chose the bounds of these intervals to exclude that $S$ has a $0$ in position $n-1$ or 2. Therefore $F_n = g(\frac n2 - 1)^2 = \mathcal F_{\frac n2 + 1}^2$.
If $n$ is odd, then $A_1$ and $A_2$ must be subsets without consecutive elements of $\{1,\dots,\frac{n+1}2\}$ and $\{2,\dots,\frac{n-3}2\}$ respectively. Therefore $F_n = g(\frac{n+1}2) \cdot g(\frac{n-5}2) = \mathcal F_{\frac{n+5}2} \cdot \mathcal F_{\frac{n-1}2}$.
When is $F_n > 100$? If $n$ is even, we need $\mathcal F_{\frac n2 + 1} > 10$, or $\frac n2 + 1 \geq 7$, which gives us 12. If $n$ is odd, we need $\mathcal F_{\frac{n+5}2} \cdot \mathcal F_{\frac{n-1}2} \geq 100$, which happes for $\mathcal F_8 \times \mathcal F_5 = 21 \cdot 5$. So we get $\frac{n+5}2 \geq 8$ or $n \geq 11$. Thus, $F_n > 100$ if and only if $n \geq 11$.