Problem
COM-B1-M10-P003 Strings of Length \(4\)
#3
★☆☆☆☆ Level 1 of 5
How many binary strings of length \(4\) contain no two adjacent ones?
Split by the last symbol.
Let \(a_n\) be the number of such strings. Then \(a_0=1\), \(a_1=2\), \(a_n=a_{n-1}+a_{n-2}\). Thus \(a_2=3\), \(a_3=5\), \(a_4=8\).
Do not confuse with stairs: the initial conditions differ.