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 Fn denote the number of friendly binary sequences with $n$ terms. Find the smallest positive integer $n$  2 such that Fn > 100.

Step 1: Let an = number of friendly sequences ending with 0

Step 2: Bn = number of friendly sequences ending with 1

Step 3: Fn = an + bn …(i)p

Step 4: Now, an + 1 = bn …(ii) (by adding 0 in the last)

Step 5: and bn + 1 = an + bn + an – 1 …(iii)

Step 6:  Fn = an + an+1 from equation (i) and equation (ii)

Step 7: and an+2 = an+1 + an + an–1 by (ii) and (iii)

Step 8:  a1 = 0, a2 = 1, a3 = 3

Step 9: So, a4 = 4, a5 = 5, a6 = 9, a7 = 16, a8 = 25, a9 = 39, a10 = 64 and a11 = 105 and so on.

Step 10: Clearly, we can see that F11 = 105.

Step 11: So, F11 > 100.