a List all the sequences of zeros and ones of length 2 that

(a) List all the sequences of zeros and ones, of length 2, that do not have both first and last element a one.

(b) List all the sequences of zeros and ones, of length 4, that do not have both first and last element a one.

(c) Suppose n 2. How many sequences of zeros and ones, of length n, are there that do not have both first and last element a one.

Solution

(a)00, 01,10

(b)0000,0001,0010,0011,0100,0101,0110,0111,1000,1010,1100, 1110

(c)2^n - (n/2)