Question

Combinatorics

Let n be a positive counting number, and consider words of length n using letters { 0 , 1 } . For example, 1011101 is such a word of length 7 , and 1001 is such a word of length 4 .

Let w(n) equal the number of words of length n with no adjacent zeros. For example, w(1) = 2 since there are two words of length 1 with no adjacent zeros: 0 and 1 . And, w(2) = 3 since there are three words of length 2 with no adjacent zeros: 01 , 10 , and 11 .

FIND w(5) and w(6)

Answer 1

16

Consider the length n binary strings with no repeated zeros

string must end in a 0 or a 1. The number of string of length n that end in a 0 is equal to the number of such sequence of length n−2 (with 10 appended). The number of string of length n that end in a 1 is equal to the number of string of length n−1(with 1 appended).

Therefore, the number of string of length n is equal to the number of string of length n−1 plus the number of string of length n−2n Thus, the Fibonacci pattern. Fn=Fn−1+Fn−2

using above discussion

w(3)=w(1)+w(2)=2+3=5

w(4)=w(2)+w(3)=3+5=8

w(5)=w(3)+w(4)=8+5=13

w(6)=w(4)+w(5)=13+8=21