Problem
COM-B1-M10-P022 Formula for Strings
#22
★★★★☆ Level 4 of 5
Prove that the number of binary strings of length \(n\) with no two adjacent ones is \(F_{n+2}\), where \(F_1=1\), \(F_2=1\).
Compare initial values and recurrence.
Let \(a_n\) be the number of such strings. As usual, \(a_n=a_{n-1}+a_{n-2}\): the string ends in \(0\) or in \(01\). Initial values are \(a_0=1\), \(a_1=2\). For Fibonacci numbers, \(F_2=1\), \(F_3=2\). Thus \(a_0=F_2\), \(a_1=F_3\), and both sequences satisfy the same recurrence. Therefore \(a_n=F_{n+2}\).
Careful indexing.