An unfriendly question about "friendly" binary sequences Question(IOQM-2022): A binary sequence is a sequence in which each term is equal to $0$ or $1$. A binary sequence is called friendly if each term is adjacent to at least one term that is equal to 1. For example, the sequence $0,1,1,0,0,1,1,1$ is friendly. Let $F_n$ denote the number of friendly binary sequences with $n$ terms. Find the smallest positive integer $n\geq 2$ such that $F_n>100$.
What I have tried till now:
1.We note that the second and the penultimate term of a friendly sequence must be $1$ as the end terms must be adjacent to $1$ for the sequence to be friendly. We can't construct new seqences out of those $n-length$ sequences that end with $0$, since we already figured out that the number at penultimate place has to be 1.
2. Suppose we have an $n$-length friendly sequence that ends with $1$. We can construct two new friendly sequence of length $n+1$ by appending a $1$ and $0$.
Using these tw0 observations, I tried to calculate $F_n$ for small values of $n$.
$F_2=1$
$F_3=3$
$(1,1,0),(0,1,1),(1,1,1)$ are the terms here. We note that we have got an extra term other than thoe that 1. and 2. made us construct. This is (0,1,1).
Note the tranformation:
$(1,1,1)\rightarrow (0,1,1)$.
3. Thus, we can take the $(n+1)$ sequences created in step 2. that end in $1$ and take the $n-1$ th term(which is $1$ here) from step 1 and replace it by zero.
Thus, if $x$ is the number of $n$-friendly sequences ending with $1$, then
$F_{n+1}=2.x+x=3x$. Further, the number of $n+1$-length friendly sequences ending with zero
will always be half the number of those ending with one.
Further, if $x=\frac{2F_n}{3}$, then, we get,
$F_{n+1}= 2F_n$
And $x=2\frac{F_n}{3}$ for $n=3$ and thus, we can proceed by induction to obtain:
$F_{n+1}=F_n.2$ for $n\geq 3$
I am skeptical about my deductions. Can anybody help me solve this problem?
 A: 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.

*

*$A_1 = \{ k : S \text{ has a 0 in position } 2k-1 \}$,

*$A_2 = \{ k : S \text{ has a 0 in position } 2k \}$.

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$.
A: Your reasoning is not quite correct.  The reason is that an $n$-friendly sequence can also be formed in a way you don't consider: by adding a $1$ to the end of a sequence of length $n-1$ that is almost friendly.  Let's call an unfriendly sequence "almost friendly" (AF) if all its bits except the last one are adjacent to a $1$.
Starting from an AF sequence of length $n$ ending in $0$, you can add a $1$ to get an AF sequence.  Starting from an AF sequence of length $n$ ending in $1$, you can add a $1$ to get a friendly sequence ending in $1$.  Starting from a friendly sequence ending in $1$, you can add either bit to get a friendly sequence.  Finally, starting from a friendly sequence ending in $0$, you can add either bit to get an AF sequence.  Defining $A_n$ (resp. $B_n$) to be the number of friendly sequences of length $n$ ending in $0$ (resp. $1$), and $C_n$ (resp. $D_n$) to be the number of almost friendly sequences of length $n$ ending in $0$ (resp. $1$), we have
$$
\begin{eqnarray}
A_{n+1} &=& B_n \\
B_{n+1} &=& B_n + D_n \\
C_{n+1} &=& A_n \\
D_{n+1} &=& A_n + C_n
\end{eqnarray}
$$
Starting with $(A_1, B_1, C_1, D_1)=(0,0,1,1)$, this gives the total ($A+B$) number of friendly sequences of length $n$ as $0, 1, 3, 4, 5, 9, 16, 25, 39, 64, 105, 169,\ldots$.  So $n=11$ is the first to exceed $100$.  (Also, this is sequence A195971 in the OEIS.)
