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 .

Step-by-step solution

Let a_n= number of friendly sequences ending with 0 B_n= number of friendly sequences ending with 1 F_n=a_n+b_n ...(i) Now, a_ n+1 =b_n ...(ii) (by adding 0 in the last) and b_ n+1 =a_n+b_n+a_ n-1 ...(iii) F_n=a_n+a_ n+1 from equation (i) and equation (ii) and a_ n+2 =a_ n+1 +a_n+a_ n-1 by (ii) and (iii) a₁=0, a₂=1, a₃=3 So, a₄=4, a₅=5, a₆=9, a₇=16, a₈=25, a₉=39, a₁₀=64 and a₁₁=105 and so on. Clearly, we can see that F₁₁=105 . So, F₁₁>100 .