The following problem is from $IOQM, 2022$, which was held today in India. This is problem number $ 22$:
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≥2 $ such that $F_n > 100$.
MY ATTEMPT:
First, I manually counted $F_1 =1$, $F_2 = 3$, and $F_3 =5$. Now, I try to find a recurrence relation on $F_n$.
Note that if $F$ is a friendly sequence, then the last three terms in $F$ can only be
101, 010, 110, 111, 011
Now, consider the sequences ending with $1$, for next term can be both $0$ or $1$, hence there are two different sequences for 1 sequence ending with 1. Similarly, there is only $1$ different sequence for each sequence ending with $0.$
Now, let $F_n$ has $a$ and $b$ sequences ending with $0$ and $1$ respectively, then $F_{n+1}$ would have respectively $b$ and $a+b$ sequences ending with $0$ and $1.$
It comes out that, $$F_n = F_{n-1} + F_{n-2}.$$
Is this solution correct?
Can someone please post a exact solution?
Thanks.
EDIT: I think the question does not acknowledge any sequence with $n=1$ term as friendly, that is $F_1=0$, since the last statement says $n≥2$. Does this make sense?