Quantrex Quantrex AcademyJEE · NEET · NDA PYQs with solutions Open app
Olympiad workbook
Exam
Olympiad workbook
Subject
IOQM
Chapter
Permutation and Combination

Olympiad workbook · IOQM · Permutation and Combination

A binary sequence is a sequence in which each term is equal to 0 or...

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,10,1,1,0,0,1,1,1 is friendly. Let FnF_n denote the number of friendly binary sequences with nn terms. Find the smallest positive integer n≥2n \geq 2 such that Fn>100F_n>100.

Correct answer

11

Step-by-step solution

Let an=a_n= number of friendly sequences ending with 0 Bn=B_n= number of friendly sequences ending with 1 Fn=an+bnF_n=a_n+b_n...(i) Now, an+1=bna_{n+1}=b_n...(ii) (by adding 0 in the last)andbn+1=an+bn+an−1and b_{n+1}=a_n+b_n+a_{n-1} ...(iii) ∵Fn=an+an+1\because \quad F_n=a_n+a_{n+1} from equation (i) and equation (ii)andan+2=an+1+an+an−1and a_{n+2}=a_{n+1}+a_n+a_{n-1} by (ii) and (iii) ∵a1=0,a2=1,a3=3\because \quad a_1=0, a_2=1, a_3=3 So, a4=4,a5=5,a6=9,a7=16,a8=25,a9=39,a10=64a_4=4, a_5=5, a_6=9, a_7=16, a_8=25, a_9=39, a_{10}=64 and a11=105a_{11}=105 and so on. Clearly, we can see that F11=105F_{11}=105. So, F11>100F_{11}>100.
Practice Permutation and Combination on Quantrex Academy →

More from Permutation and Combination

All Permutation and Combination questions Full Permutation and Combination list All Olympiad workbook PYQs